2D Array Traversals: Study Guide (Computer Science A 4.12)

Why traversal needs two loops

A 1D array has one index, so one loop visits every element. A 2D array has two indices, so you need two loops: one to choose a row and one to choose a column. A loop inside a loop is a nested iteration. Because a 2D array is an array of arrays, the loops are the 1D loops you already know, one nested in the other.

Which loop goes outside decides the order in which elements are visited.

• Row-major order: the outer loop chooses a row; the inner loop runs across all columns of that row. Every element of row 0 is visited, then every element of row 1, and so on. This is the usual reading order.
• Column-major order: the outer loop chooses a column; the inner loop runs down all rows of that column.
• A uniquely defined order: any other pattern, such as every other row, a diagonal or a snake.

Row-major and column-major with index loops

Take int[][] m = { {1, 2, 3}, {4, 5, 6} };, 2 rows and 3 columns.

// row-major
for (int r = 0; r < m.length; r++)
{
    for (int c = 0; c < m[r].length; c++)
    {
        System.out.print(m[r][c] + " ");
    }
}

This prints 1 2 3 4 5 6. Figure 1 numbers the cells in visiting order.

// column-major
for (int c = 0; c < m[0].length; c++)
{
    for (int r = 0; r < m.length; r++)
    {
        System.out.print(m[r][c] + " ");
    }
}

This prints 1 4 2 5 3 6 (Figure 2).

Look at the two header lines. Whichever way you nest the loops, r always indexes rows and c always indexes columns, and in the element access the row index always comes first: m[r][c]. What changes is which loop is outside. The bound for r is the number of rows, m.length. The bound for c is the number of columns, m[0].length (or m[r].length inside a row-major loop).

The bound error. On a non-square array it matters which bound goes with which variable. Running a loop that used r < m2[0].length (3) for the rows of a 2-by-3 array prints 1 2 4 5 and then threw java.lang.ArrayIndexOutOfBoundsException when r reached 2, since there is no row 2.

Nested enhanced for loops

int sum = 0;
for (int[] row : m)
{
    for (int v : row)
    {
        sum += v;
    }
}

This traverses in row-major order. The rules:

• The outer loop goes through the rows, so its variable must have the type of a row, which is int[].
• The inner loop goes through one row, so its variable has the type of the elements in the row, int.
• For a String[][] the types would be String[] and String.

The sum of m is 21 (run and confirmed). The enhanced loop cannot go in column-major order and gives you no row or column numbers. If you need either, use index loops.

What can and cannot be changed. The inner variable v is a copy of the element, so v = 0; has no effect. In the run for (int[] row : m) for (int v : row) v = 0; left m as 1 2 3 | 4 5 6 |. The outer variable row is a reference to the real row, so row[0] = 0; does change the array: after for (int[] row : m) row[0] = 0; the array was 0 2 3 | 0 5 6 |. To assign to every element in a reliable, readable way, use index loops: m[r][c] = 0;.

Worked example 1: row sums and column sums

Task. For the 3-row, 4-column array data, compute an array of row sums and an array of column sums.

int[][] data = { {3, 1, 4, 1}, {5, 9, 2, 6}, {5, 3, 5, 8} };

Row sums (row-major).

public static int[] rowSums(int[][] m)
{
    int[] sums = new int[m.length];
    for (int r = 0; r < m.length; r++)
    {
        for (int c = 0; c < m[r].length; c++)
        {
            sums[r] += m[r][c];
        }
    }
    return sums;
}

The result array has one slot per row, and the new int[] starts at zeros, so += works from the first element.

Row	Elements	Row sum
0	3, 1, 4, 1	9
1	5, 9, 2, 6	22
2	5, 3, 5, 8	21

Column sums (column-major). The sums array needs one slot per column, so its length is m[0].length.

public static int[] colSums(int[][] m)
{
    int[] sums = new int[m[0].length];
    for (int c = 0; c < m[0].length; c++)
    {
        for (int r = 0; r < m.length; r++)
        {
            sums[c] += m[r][c];
        }
    }
    return sums;
}

Column	Elements	Column sum
0	3, 5, 5	13
1	1, 9, 3	13
2	4, 2, 5	11
3	1, 6, 8	15

Check. The row sums add to 9 + 22 + 21 = 52 and the column sums add to 13 + 13 + 11 + 15 = 52. Both must equal the sum of the whole table. The run printed 9 22 21 / 13 13 11 15.

Worked example 2: filling from a formula, snake order and diagonals

Filling. Build a 2-row, 3-column table whose element in row r, column c is r * 3 + c.

int[][] g = new int[2][3];
for (int r = 0; r < g.length; r++)
{
    for (int c = 0; c < g[0].length; c++)
    {
        g[r][c] = r * 3 + c;
    }
}

Trace: row 0 gets 0, 1, 2; row 1 gets 3, 4, 5. The program printed 0 1 2 | 3 4 5 | and g[1][2] is 5. The formula numbers the cells 0 to 5 in row-major order.

Snake order. Visit even rows left to right and odd rows right to left, for int[][] sq = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };.

for (int r = 0; r < sq.length; r++)
{
    if (r % 2 == 0)
    {
        for (int c = 0; c < sq[r].length; c++) { System.out.print(sq[r][c] + " "); }
    }
    else
    {
        for (int c = sq[r].length - 1; c >= 0; c--) { System.out.print(sq[r][c] + " "); }
    }
}

Row	Direction	Visited
0	left to right	1 2 3
1	right to left	6 5 4
2	left to right	7 8 9

The output was 1 2 3 6 5 4 7 8 9.

Diagonals of a square array. The main diagonal has equal row and column: sq[i][i], giving 1 + 5 + 9 = 15. The other diagonal has sq[i][sq.length - 1 - i], giving 3 + 5 + 7 = 15. These need only one loop, because the column is computed from the row. (Both totals matched the run.)

Building a new 2D array

A traversal can read one array and write another. To transpose a table (swap rows and columns), make the new array with the sizes swapped and copy each element to the mirrored position:

int[][] t = new int[m[0].length][m.length];
for (int r = 0; r < m.length; r++)
{
    for (int c = 0; c < m[0].length; c++)
    {
        t[c][r] = m[r][c];
    }
}

For { {1, 2, 3}, {4, 5, 6} } this produced a 3-row, 2-column array 1 4 | 2 5 | 3 6 |.

Common misconceptions

• “The loops can be nested either way for the same output.” The order of nesting changes the visiting order, which changes any printed output and any algorithm that depends on order.
• “The inner bound is always m.length.” It is m[r].length or m[0].length, the number of columns.
• “The outer enhanced for variable is an int.” It is an int[], a whole row.
• “Assigning to the enhanced for variable updates the array.” It only changes the copy.
• “row[0] = 0 inside the outer enhanced loop is also a copy.” It changes the real array; row refers to the real row.
• “m[c][r] is the same as m[r][c].” Reversing the indices reads a different cell, and fails on non-square arrays.
• “A diagonal needs nested loops.” One loop with a computed column is enough.

Where this leads

Topic 4.13 builds the standard algorithms (maximum, sum, count, any, all, duplicates, shift, reverse) on row, column and whole-table traversals. The sort and search topics that follow work on 1D collections, and a 2D linear search simply searches each row in turn. 2D traversal is also directly tested as a free-response question. Practise with the Topic 4.12 practice questions, recap with the revision notes and tick off the checklist. Next: the Topic 4.13 study guide on 2D array algorithms.