Introduction
Accessing individual elements in 2D arrays is straightforward, but most algorithms require processing all elements systematically. Traversing a 2D array means using nested iteration statements to access all or an ordered sequence of elements in the array.
Topic 4.12 covers different traversal patterns: row-major order (processing across rows), column-major order (processing down columns), and using enhanced for loops with 2D arrays. Understanding these patterns is essential for the 2D array free-response question on the AP exam.
Why Nested Loops?
Since 2D arrays are stored as arrays of arrays, the way 2D arrays are traversed using for loops and enhanced for loops is similar to 1D array objects—but we need nested loops to handle two dimensions.
Think of it as:
- Outer loop: selects which row to process
- Inner loop: processes all columns in that row
Row-Major Order Traversal
Row-major order refers to an ordering of 2D array elements where traversal occurs across each row.
This is the most common traversal pattern: process all columns in row 0, then all columns in row 1, and so on.
Standard Row-Major Pattern
Output:
1 2 3
4 5 6
7 8 9
Pattern breakdown:
- Outer loop: row goes from 0 to matrix.length - 1
- Inner loop: col goes from 0 to matrix[0].length - 1
- Access element at matrix[row][col]
Order of access: (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)
Example: Sum All Elements
int[][] numbers = {
{5, 10, 15},
{20, 25, 30}
};
int sum = 0;
for (int r = 0; r < numbers.length; r++)
{
for (int c = 0; c < numbers[0].length; c++)
{
sum += numbers[r][c];
}
}
System.out.println("Sum: " + sum); // 105
Column-Major Order Traversal
Column-major order traversal occurs down each column. Process all rows in column 0, then all rows in column 1, and so on.
Standard Column-Major Pattern
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
for (int col = 0; col < matrix[0].length; col++)
{
for (int row = 0; row < matrix.length; row++)
{
System.out.print(matrix[row][col] + " ");
}
System.out.println();
}
Output:
1 4 7
2 5 8
3 6 9
Pattern breakdown:
- Outer loop: col goes from 0 to matrix[0].length - 1
- Inner loop: row goes from 0 to matrix.length - 1
- Access element at matrix[row][col]
Order of access: (0,0), (1,0), (2,0), (0,1), (1,1), (2,1), (0,2), (1,2), (2,2)
Key difference: Switch the outer and inner loop variables compared to row-major.
Example: Find Column Sums
int[][] data = {
{10, 20, 30},
{5, 15, 25},
{8, 12, 18}
};
for (int col = 0; col < data[0].length; col++)
{
int colSum = 0;
for (int row = 0; row < data.length; row++)
{
colSum += data[row][col];
}
System.out.println("Column " + col + " sum: " + colSum);
}
// Column 0 sum: 23
// Column 1 sum: 47
// Column 2 sum: 73
Enhanced For Loop with 2D Arrays
The outer loop of a nested enhanced for loop used to traverse a 2D array traverses the rows. Therefore, the enhanced for loop variable must be the type of each row, which is a 1D array.
The inner loop traverses a single row. Therefore, the inner enhanced for loop variable must be the same type as the elements stored in the 1D array.
Enhanced For Loop Pattern
int[][] grid = {
{1, 2, 3},
{4, 5, 6}
};
for (int[] row : grid) // Outer: each row (1D array)
{
for (int element : row) // Inner: each element in row
{
System.out.print(element + " ");
}
System.out.println();
}
Output:
1 2 3
4 5 6
Type breakdown:
- grid is int[][] (2D array of ints)
- Each row is int[] (1D array of ints)
- Each element is int (primitive value)
Example: Finding Maximum
int[][] values = {
{23, 45, 12},
{67, 34, 89},
{21, 56, 43}
};
int max = values[0][0];
for (int[] row : values)
{
for (int val : row)
{
if (val > max)
{
max = val;
}
}
}
System.out.println("Max: " + max); // 89
Enhanced For Loop Limitation
Assigning a new value to the enhanced for loop variable does not change the value stored in the array.
int[][] nums = {{1, 2}, {3, 4}};
for (int[] row : nums)
{
for (int val : row)
{
val = val * 2; // Does NOT change array!
}
}
// nums is still {{1, 2}, {3, 4}}
Why? The loop variable is a copy, not a reference to the array position.
To modify elements, use indexed loops:
for (int r = 0; r < nums.length; r++)
{
for (int c = 0; c < nums[0].length; c++)
{
nums[r][c] = nums[r][c] * 2; // This works!
}
}
// nums is now {{2, 4}, {6, 8}}
Other Traversal Patterns
Nested iteration statements can be written to traverse the 2D array in a uniquely defined order beyond row-major and column-major.
Diagonal Traversal
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
// Main diagonal: (0,0), (1,1), (2,2)
for (int i = 0; i < matrix.length; i++)
{
System.out.print(matrix[i][i] + " ");
}
// Output: 1 5 9
Reverse Row Order
// Traverse from last row to first row
for (int row = matrix.length - 1; row >= 0; row--)
{
for (int col = 0; col < matrix[0].length; col++)
{
System.out.print(matrix[row][col] + " ");
}
System.out.println();
}
// Output:
// 7 8 9
// 4 5 6
// 1 2 3
Border Traversal
int[][] grid = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
// Top row
for (int c = 0; c < grid[0].length; c++)
{
System.out.print(grid[0][c] + " ");
}
// Right column (skip top-right corner already printed)
for (int r = 1; r < grid.length; r++)
{
System.out.print(grid[r][grid[0].length - 1] + " ");
}
// Output: 1 2 3 4 8 12
Converting Between Row-Major and Column-Major
Any row-major algorithm can be converted to column-major by swapping the loop order:
Row-major:
for (int r = 0; r < arr.length; r++)
{
for (int c = 0; c < arr[0].length; c++)
{
// process arr[r][c]
}
}
Column-major:
for (int c = 0; c < arr[0].length; c++)
{
for (int r = 0; r < arr.length; r++)
{
// process arr[r][c]
}
}
Common Mistakes
Mistake 1: Wrong loop bounds
// WRONG - uses same bound for both loops
for (int r = 0; r < arr.length; r++)
{
for (int c = 0; c < arr.length; c++) // Should be arr[0].length
{
// ...
}
}
Mistake 2: Confusing enhanced for loop types
// WRONG - element should be int[], not int
for (int row : grid) // Type mismatch if grid is int[][]
{
// ...
}
// CORRECT
for (int[] row : grid)
{
// ...
}
Mistake 3: Trying to modify with enhanced for
// WRONG - doesn't modify array
for (int[] row : matrix)
{
for (int val : row)
{
val = 0; // Creates copy, doesn't change array
}
}