The AP Computer Science A 5-hour live stream review is here!Β πŸ’»

Join us on May 5, 2021 for the 🌢️ AP Computer Science A Cram Finale for a last minute review to get all your questions answered!

πŸ“š

All Subjects

Β >Β 

πŸ’»Β 

AP Comp Sci A

Β >Β 

πŸ’»

Unit 8

8.2 Traversing 2D Arrays

12 min readβ€’november 16, 2020

Peter Cao

Caroline Koffke


8.2 Traversing 2D Arrays

Note: In this topic, we will be using arrayB and the graphical representation of 2D arrays from the previous topic. As a reminder, here is arrayB:
int[][] arrayB = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};

General Form

Recall that when traversing a 1D array, you use a loop, usually a for loop or enhanced for loop. This is similar to how we traverse 2D arrays, except in 2D arrays, we need 2 nested for loops, an outer loop traversing through one dimension, and an inner loop traversing through the other. Here is the general form:
for (firstDimension traversal conditions) { for (secondDimension traversal conditions) { System.out.print(item + " "); } } System.out.println();

Row-Wise vs. Column-Wise

There are two main directions we can traverse through. The first is row-wise traversal, traversing through every element in one row before moving to the next. Conversely, there is column-wise traversal, traversing through every element in one column before moving on to the next.

Row-wise Traversal

https://firebasestorage.googleapis.com/v0/b/fiveable-92889.appspot.com/o/images%2F-GxHKbL2KFRU5.png?alt=media&token=ee0244d4-8e99-41da-bcf5-de34b73d42c6

Column-wise Traversal

https://firebasestorage.googleapis.com/v0/b/fiveable-92889.appspot.com/o/images%2F-6nj8VoEDvTyP.png?alt=media&token=ff647c88-0f1d-468d-9f8b-0ff98838ed34
We will focus on traversing in a forward direction (from left-to-right and from top-to-bottom) in this section. In the next, we will go in reverse directions, but this will only require a change in the for loop conditional.

Row-Wise Traversal

When doing row-wise traversal, the outer loop traverses through the different rows, and the inner loop traverses through the elements in each row. Here is how you write code for this:
public static void rowWiseForward(int[][] array) { for (int i = 0; i < array.length; i++) { for (int j = 0; j < array[0].length; j++) { System.out.print(array[i][j] + " "); } } } public static void main(str[] args) { columnWiseForward(arrayB); }
1 2 3 4 5 6 7 8 9 10 11 12
We can only use nested enhanced for loops for forward row-wise traversals. Here is the code that creates the same output as above, only this time using enhanced for loops instead of regular for loops:
public static void rowWiseForwardEnhancedForLoops(int[][] array) { for (int[] row: array) { for (int number: row) { System.out.print(number + " "); } } }
Remember that the type of the rows in the 2D array are 1D arrays, and the rows contain elements of a certain type!

Column-Wise Traversal

When doing column-wise traversal, the outer loop traverses through the different columns, and the inner loop traverses through the elements in each columns. Here is how you write code for this:
public static void columnWiseForward(int[][] array) { for (int i = 0; i < array[0].length; i++) { for (int j = 0; j < array.length; j++) { System.out.print(array[j][i] + " "); } } } public static void main(str[] args) { columnWiseForward(arrayB); }
1 5 9 2 6 10 3 7 11 4 8 12

In Summary

We can see that the two traversal algorithms using regular for loops are almost the same. The only significant difference is with the order of the for loop conditionals. However, the loop conditional for traversing through different rows is the same in both cases, and so is the conditional for traversing through different columns. Here are the conditionals for the two different traversal directions:
To traverse through different rows: i < array.length;
To traverse through different columns: i < array[0].length;
We will use this to help us go in reverse next!

Going In Reverse

Sometimes, we want to traverse across the rows from right to left, or traverse across the columns from bottom to top. This will require a change the for loop headers, as follows:
To traverse through different rows: int i = array.length() - 1; i >= 0; i--
This is initializing i to the last row, and then going up row-by-row to the first row in every loop iteration.
To traverse through different columns: int i = array[0].length - 1; i >= 0; i--
Likewise, this is initializing i to the rightmost column, and then going left column-by-column to the first column in every loop iteration.
To do row-wise traversal, put the row for loop header first, while to do column-wise traversal, put the column for loop header first.

Challenge Example: Snaking Around

Let's do a challenge. We want to traverse arrayB so that it prints the following:
1. 1 2 3 4 8 7 6 5 9 10 11 12 2. 12 8 4 3 7 11 10 6 2 1 5 9
For example 1, we are doing a row-wise traversal from top to bottom that starts forward, but then alternates the direction every row as shown in this image:
https://firebasestorage.googleapis.com/v0/b/fiveable-92889.appspot.com/o/images%2F-OrLuYC2Tizoe.png?alt=media&token=c3e61da8-bf50-42d9-8a61-6c3154bb6118
For example 2, we are doing a column-wise traversal from right to left that starts backwards then alternates in direction as is shown in this image:
https://firebasestorage.googleapis.com/v0/b/fiveable-92889.appspot.com/o/images%2F-sgLIe92rhWKU.png?alt=media&token=dbb0e8e2-7b30-4ab5-8a44-2af48cd91303
What's the secret behind this? It's an if statement and modulo. Here is the code with the this part commented:
public static void exampleOne(int[][] array) { for (int i = 0; i < array.length; i++) { if (i % 2 == 0) { // we use an if statement with modulo base 2 to alternate for (int j = 0; j < array[0].length; j++) { System.out.print(array[i][j] + " "); } } else { for (int j = array[0].length - 1; j >= 0; j--) { System.out.print(array[i][j] + " "); } } } } public static void exampleTwo(int[][] array) { for (int i = array[0].length; i >= 0; i--) { if (i % 2 == 0) { // we use an if statement with modulo base 2 to alternate for (int j = 0; j < array[0].length; j++) { System.out.print(array[j][i] + " "); } } else { for (int j = array.length - 1; j >= 0; j--) { System.out.print(array[j][i] + " "); } } } }

Standard Algorithms Using Traversals

For 2D arrays, we use the slightly modified versions of the algorithms we have been doing with 1D arrays and ArrayLists. All of these algorithms apply the loop traversals we have just discussed! Here, we will have a snippet for each algorithm you are expected to know with each snippet annotated for you.

Sequential/Linear Search

/** Prints the row and column indices if the element is in the array and -1 if not */ public static boolean searchForElement(int[][] array, int elementToSearch) { flag = false; //sets flag to see if element has been found for (int i = 0; i < array.length; i++) { for (int j = 0; j < array[0].length; j++) { //traverses through the array if (array[i][j] == elementToSearch) { System.out.println("Row " + i); System.out.println("Column " + j); //if element found, print coordinates flag = true; //element has been found } } } if (!flag) { //if element not found, print -1 System.out.println(-1); } }

Modifying Array Values

/** Doubles each element of the array */ public static void doubleArray(int[][] array) { for (int i = 0; i < array.length; i++) { for (int j = 0; j < array[0].length; j++) { array[i][j] *= 2; // doubles each individual element } } }
Note that in the above snippet, we used regular for loops instead of enhanced for loops. Here, we cannot use enhanced for loops as follows:
/** Doubles each element of the array */ public static void doubleArray(int[][] array) { for (int[] row: array) { for (int number: row) { number *= 2; // doubles number } } }
This is because Java is pass-by-value. In the first example, we are actually accessing the array itself. However, in the enhanced for loop example, we are making a copy of that array and any changes are affecting the copy, not the actual array.
However, if the array items are objects and we are changing the value of one of the object's instance variables, we can use enhanced for loops as the copy contains references to the actual objects themselves. Here is an example of this:
/** Represents a student */ public class Student { private String name; /** Sets the name of the Student */ public void setName(String name) { this.name = name; } /** Other instance variables, methods, and constructors not shown */ } // IN ANOTHER CLASS /** Resets names of all student s */ public static void doubleArray(Student[][] array, String defaultName) { for (Student[] row: array) { for (Student student: row) { student.setName(defaultName); // Sets each student's name to a default name } } }

Putting all the Values Into an ArrayList

/** Inserts all the values in the array into an ArrayList */ public static ArrayList<Integer> putIntoArrayList(int[][] array) { ArrayList<Integer> intList = new ArrayList<Integer>(); //makes an empty ArrayList for (int[] row: array) { for (int number: row) { intList.add(new Integer(number)); //Boxes the integer to an Integer object } //adding it to the ArrayList } return intList; }

Putting all the Values Into an Array

/** Inserts all the values in the array into an ArrayList */ public static int[] putIntoArray(int[][] array) { int[] intArray = new int[array.length * array[0].length]; //initialize the array for (int i = 0; i < array.length; i++) { //to the number of items in rect array for (int j = 0; j < array[0].length; j++) { intArray[i*array[0].length + j] = array[i][j]; //i*array[0].length + j } //is the nth item } return intArray; }

Finding the Minimum and Maximum

/** Finds the maximum */ public static int maximum(int[][] array) { int maxValue = array[0][0]; for (int[] row: array) { for (int number: row) { if (number > maxValue) { //if new max value found, replace current maxValue maxValue = number; } } } return maxValue; } /** Finds the minimum */ public static int minimum(int[][] array) { int minValue = array[0][0]; for (int[] row: array) { for (int number: row) { if (number < minValue) { //if new min value found, replace current minValue minValue = number; } } } return minValue; }
A common mistake is initializing the maxValue and minValue to 0. If all the values in the array are positive, it would incorrectly keep minValue at 0 (all the values are greater than 0, leaving 0 as the minimum). If all the values in the array are negative, it would incorrectly keep maxValue at 0 (all the values are less than 0, leaving 0 as the maximum). To counter these errors, initialize these to the first value in the array.

Finding a Sum

/** Sums up all elements in the array */ public static int sum(int[][] array) { int sum = 0; for (int[] row: array) { for (int number: row) { sum += number; //adds every element to sum } } return sum; }

Finding a Mean

/** Finds the mean/average of the array */ public static int mean(int[][] array) { int sum = sum(array); // find the sum of the array, can be replaced with sum return (double) sum / (array.length * array[0].length); //algorithm above }

Finding a Mode

/** Finds the mode of an array Prerequisite: The array must have a mode */ public static int mode(int[][] array) { int[] newArray = putIntoArray(array) //places the numbers into a 1D array as above int mostCommon = 0; int mostCommonFrequency = 0; for (int i = 0; i < newArray.length - 1; i++) { //traverse through the new array int currentFrequency = 1; for (int j = i + 1; j < newArray.length; j++) { //traverse through rest of array if (newArray[j] == newArray[i]) { // if any element matches current element currentFrequency++; // being checked, add 1 to frequency } } if (currentFrequency > mostCommonFrequency) { mostCommon = newArray[i]; // replaces current mode if new most common element mostCommonFrequency = currentFrequency; } } return mostCommon; // can also be modified to return the frequency }

Determining If All Values Have a Certain Property

/** Determines whether all values are even */ public static boolean isEven(int[][] array) { //Assume all values are positive first for (int[] row: array) { for (int number: row) { if (number % 2 == 1) { //If there is one value that is not positive, return false return false; } } } return true; //No odd numbers were found }

Accessing All Consecutive Pairs/Triplets/Sequences of Length n of Elements

/** Returns all consecutive sequences of length n in the array */ public static void returnAllConsecutiveSequences(int[][] array, int length) { public int[] oneDArray = putIntoArray(array); for (int i = 0; i <= oneDArray.length - length; i++) { for (int j = 0; j < length; j++) { System.out.print(oneDArray[i+j] + " "); //2 loops, one to get the starting number } //the other to go through the sequences System.out.println(); } }

Checking if There are Duplicate Elements

/** Checks to see if there are duplicate elements */ public static boolean duplicates(int[][] array) { int[] newArray = putIntoArray(array) //places the numbers into a 1D array as above for (int i = 0; i < newArray.length - 1; i++) { //traverse through the new array for (int j = i + 1; j < newArray.length; j++) { //traverse through rest of array if (newArray[j] == newArray[i]) { // if any element matches current element return true; // being checked, return true } } } return false; // if this point reached, no duplicates found }

Determining How Many Elements Fit a Criteria

/** Returns how many even numbers there are */ public static int evenFrequency(int[][] array) { int numberEven = 0; for (int[] row: array) { for (int number: row) { if (number % 2 == 0) { numberEven++; // increments every time an even integer is found } } } return numberEven; }

Was this guide helpful?

πŸ’ͺ🏽 Are you ready for the Comp Sci exam?
Take this quiz for a progress check on what you’ve learned this year and get a personalized study plan to grab that 5!
START QUIZ
Hours Logo
Studying with Hours = the ultimate focus mode
Start a free study session
FREE AP comp sci a Survival Pack + Cram Chart PDF
Sign up now for instant access to 2 amazing downloads to help you get a 5
Browse Study Guides By Unit
πŸ™
Exam Reviews
πŸ–±
Unit 10: Recursion
βž•
Unit 1: Primitive Types
πŸ“±
Unit 2: Using Objects
πŸ–₯
Unit 3: Boolean Expressions and if Statements
πŸ•Ή
Unit 4: Iteration
βš™οΈ
Unit 5: Writing Classes
⌚️
Unit 6: Array
πŸ’Ύ
Unit 7: ArrayList
πŸ–²
Unit 9: Inheritance
Join us on Discord
Thousands of students are studying with us for the AP Computer Science A exam.
join now
πŸ“± Stressed or struggling and need to talk to someone?
Talk to a trained counselor for free. It's 100% anonymous.
Text FIVEABLE to 741741
Β© 2021 Fiveable, Inc.