AP® Computer Science A review sheet from Aim for Five (aimforfive.com/csa/units/4/4-12)
Unit 4 · Topic 4.12
4.12 2D Array Traversals
To visit every element of a 2D array, you use nested loops. This topic covers row-major order, column-major order, nested enhanced for loops, and how to trace traversals that go backward or skip rows and columns.
Key terms
- nested loops
- row-major order
- column-major order
- enhanced
forover rows
Row-major order
Row-major order goes across each row, left to right, before moving down to the next row, the way you read a page. The outer loop picks the row and the inner loop moves across its columns:
int[][] g = { {1, 2, 3}, {4, 5, 6} };
for (int r = 0; r < g.length; r++)
{
for (int c = 0; c < g[0].length; c++)
{
System.out.print(g[r][c] + " ");
}
}
System.out.println();
for (int c = 0; c < g[0].length; c++)
{
for (int r = 0; r < g.length; r++)
{
System.out.print(g[r][c] + " ");
}
}
System.out.println();
With { {1, 2, 3}, {4, 5, 6} }, the first pair of loops prints 1 2 3 4 5 6 .
Column-major order
Column-major order goes down each column before moving right to the next column. Swap the loops: the outer loop picks the column and the inner loop moves down the rows. The second pair of loops above prints 1 4 2 5 3 6 .
Watch the bounds when you swap. The row index is always checked against g.length and the column index against g[0].length, whichever loop it's in. And the element is still g[r][c], row first, even when the column loop is on the outside.
Nested enhanced for loops
Since a 2D array is an array of rows, the outer enhanced for variable is a whole row, so its type is a 1D array like int[]. The inner variable is one element of that row, so its type matches the elements, like int.
Enhanced for loops always go in row-major order, and the same copy rule from 4.4 applies: assigning to the inner variable doesn't change the array. If the elements are objects, though, calling a mutator on the inner variable does change the object in the grid, just as in 1D.
Use enhanced for loops when you only need to read every element, for example to add up the whole grid or count matches. Use indexed loops when you need positions, neighbors, a single column, or to change elements.
Other orders
A full traversal of a grid with R rows and C columns visits R * C elements, whichever order you use. You can traverse in any order the problem needs: bottom row first, every other column, just one row, just the border. Change the loops' starting values, conditions and updates. When tracing, list the values of the outer variable first, then for each one, the inner variable's values.
Worked examples
Try each one yourself first, then open the solution.
- Example 1
Enhanced for over a 2D array
What does this code print?
int[][] g = { {1, 2, 3}, {4, 5, 6} }; int total = 0; for (int[] row : g) { for (int value : row) { total += value; value = 0; } } System.out.println(total + " " + g[1][2]);Show the solutionHide the solution
- Step 1: The outer loop's
rowis first {1, 2, 3}, then {4, 5, 6}. The inner loop'svalueis each element of that row. - Step 2:
totaladds all six elements: 1 + 2 + 3 + 4 + 5 + 6 = 21. - Step 3:
value = 0only changes the copy, so the array keeps its values.g[1][2]is still 6.
Answer: It prints
21 6. - Step 1: The outer loop's
- Example 2
A custom order
What does this code print?
int[][] g = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; for (int r = g.length - 1; r >= 0; r--) { for (int c = 0; c < g[0].length; c += 2) { System.out.print(g[r][c] + " "); } } System.out.println();Show the solutionHide the solution
- Step 1: The outer loop goes through the rows from the bottom:
r= 2, 1, 0. - Step 2: The inner loop visits columns 0 and 2 (
c += 2skips column 1). - Step 3: Row 2 gives 7 and 9, row 1 gives 4 and 6, row 0 gives 1 and 3.
Answer: It prints
7 9 4 6 1 3. - Step 1: The outer loop goes through the rows from the bottom:
Common mistakes
- Writing
g[c][r]when the column loop is on the outside. The element is alwaysg[row][col]. - Checking the column index against
g.length(the number of rows). Useg[0].lengthfor columns. - Giving the outer enhanced
forvariable the element type, likeint, instead of the row type, likeint[].
On the exam
- Expect questions that show a nested loop and ask for the printed order, or which loops print the elements in column-major order. Trace the first few values, then check the pattern.
Connected topics
Videos
Check yourself
4 questions on 4.12 2D Array Traversals. Pick an answer to see if you got it, and why.
Consider the following code segment.int[][] m = {{1, 2, 3}, {4, 5, 6}};
for (int c = 0; c < m[0].length; c++)
{
for (int r = 0; r < m.length; r++)
{
System.out.print(m[r][c]);
}
}What is printed as a result of executing the code segment?
Consider the following code segment.int[][] m = {{2, 4}, {6, 8}, {1, 3}};
int total = 0;
for (int[] row : m)
{
for (int v : row)
{
if (v > 2)
{
total += v;
}
}
}
System.out.println(total);What is printed as a result of executing the code segment?
Assume grid is a 2D array of double values. Which of the following loop headers can be used as the outer loop of a nested enhanced for loop that visits every value in grid?
Consider the following code segment.int[][] m = {{1, 2}, {3, 4}};
for (int[] row : m)
{
for (int v : row)
{
v = 0;
}
row[0] = 5;
}
System.out.println(m[0][0] + m[0][1] + m[1][0] + m[1][1]);What is printed as a result of executing the code segment?
0 of 4 answered