2D Array Traversals
Introduced| English |
|---|
| nested loops/ˈnestɪd luːps/ |
| row-major order/rəʊ ˈmeɪdʒə ˈɔːdə/ |
| enhanced for/enˈhænst fɔː/ |
A rectangular grid exposes the wrong loop bound
- A grid has two rows and three columns. A loop bounded by g.length for both indices visits only the first two columns.
- Use r < g.length and, for each row, c < g[r].length. This also handles rows of different lengths, while g[0].length assumes a nonempty rectangular grid.
Nested loops for a grid
- To visit every cell of a 2-D array, use nested loops 嵌套循环 (from Unit 2). Outer loop over rows, inner loop over columns:
for (int r = 0; r < g.length; r++) { for (int c = 0; c < g[r].length; c++) { ... g[r][c] ... } }The inner loop sweeps a full row before the outer moves to the next.
Row-major order
- This nesting visits cells in row-major order 行主序: all of row 0, then row 1, …
g[0][0], g[0][1], …, g[1][0], g[1][1], … - It's the natural reading order — left to right, top to bottom. For a nonempty rectangular grid, columns can instead be the outer loop to visit cells column by column. A ragged array needs an explicit policy for columns that some rows do not contain.
The for-each version
- An enhanced for 增强循环 loop over a 2-D array gives one row (a 1-D array) at a time.
for (int[] row : g) { for (int x : row) { ... x ... } } - The outer variable is a whole row; the inner walks that row's values. The primitive loop variable does not update stored cells when reassigned. The row variable is still a reference, so an indexed inner loop can modify
row[c].
Row-major traversal
Outer loop over rows, inner over columns: 1,2,3,4,5,6.
Which pattern shown here visits every cell of a non-null 2-D int array whose row references are all non-null?
Outer over rows, inner over columns.
The outer loop of the shown row-major 2-D traversal should be bounded by...
The outer row loop uses g.length; the inner cell loop uses g[r].length, which handles unequal row lengths.
For a 2-row, 3-column grid, how many cells does the nested loop visit?
rows × columns = 2 × 3 = 6.
Row-major traversal visits cells in the order...
Row-major = left to right, top to bottom.
In for (int[] row : g), the variable row is...
The outer for-each variable is a row array.
Using g.length for both loop bounds always throws an exception on any non-square rectangular grid.
False: in a 2-row, 3-column grid it visits only two columns and silently misses cells. In a taller-than-wide grid it can instead run past a row boundary.
Bounding correctly
- Outer bound:
r < g.length(rows). Inner bound:c < g[r].length(the current row's length). Using the wrong length for a loop is a subtle bug in non-square grids. - For a nonempty rectangular grid,
g[0].lengthalso gives the common column count, and the inner body runsrows × columnstimes. For ragged rows, add the row lengths; all row references must be non-null.
Use g.length for rows and g[r].length for the current row's cells. Using the row count as both bounds can skip columns in a wide grid or run out of bounds in a tall grid. An empty outer array needs no access to g[0]; a null row needs an explicit handling policy before reading its length.
Order the cells visited in row-major traversal of a 2×2 grid.
The inner loop finishes one row before the outer loop advances.
For int[][] g = {{1, 2, 3}, {}, {4}};, how many cells does the per-row traversal visit?
Add the row lengths: 3 + 0 + 1 = 4. The empty row contributes no cells.
Summing a 2-D array:
for (int r = 0; r < g.length; r++)for (int c = 0; c < g[r].length; c++)sum += g[r][c];— visits all cells row by row, assuming no row is null.
Carry the reasoning to a new case
- For
int[][] g = {{1, 2, 3}, {}, {4}};, the row lengths are 3, 0 and 1. The per-row bounds visit four cells and sum to 10;g[0].lengthis not a valid bound for every row. - You can modify row[c] with an indexed inner loop; reassigning a primitive x in an inner enhanced loop does not update a cell.
Traverse a 2-D array with nested loops: outer over rows (r < g.length), inner over columns (c < g[r].length), accessing g[r][c]. This visits cells in row-major order (the sum of row lengths; rows × columns for a rectangular grid). An enhanced for (for (int[] row : g)) hands a reference to one row at a time; assigning to a primitive inner-loop variable does not change a stored cell.