2D Array Traversals

A small movie theater keeps track of tickets sold in a 2D array: one row per day, one column per showtime. With what you know from Topic 4.11, you can read any single value, such as tickets[1][2]. But the manager wants to see the whole table printed, or to add 2 tickets to every entry after finding a stack of paper sales. Writing one statement per element would work for 6 elements and fail completely for 600. You need a way to traverse the 2D array: to visit every element, one at a time, in a planned order.

For a 1D array, one loop was enough (Topic 4.4): an index runs from 0 up to length - 1. A 2D array needs two indexes, a row and a column, so it needs two loops, one inside the other. This is exactly the nested iteration from Topic 2.11, and the rule you learned there decides the order: the inner loop finishes all of its iterations before the outer loop moves on.

Here is the most common plan. The outer loop picks a row. While that row is held steady, the inner loop walks across it, column by column. When the inner loop reaches the end of the row, the outer loop moves down to the next row and the inner loop starts over at column 0. You read a page of a book the same way: across a line from left to right, then down to the next line.

Visiting a 2D array this way, across each row before moving down to the next row, is called row-major order.

The pattern has a fixed shape. Each part has a job:

for (int row = 0; row < grid.length; row++)
{
    for (int col = 0; col < grid[0].length; col++)
    {
        // use grid[row][col]
    }
}

• row < grid.length: grid.length is the number of rows (the length of the outer array), so row takes every valid row index, 0 up to one less than the number of rows.
• col < grid[0].length: grid[0] is the first row, a 1D array, and its length is the number of columns. Every row of an AP-style 2D array has the same length, so grid[row].length gives the same number and also works.
• grid[row][col]: the row index always comes first, matching the order of the loops.
• <, not <=: the last valid index is one less than the length, exactly as in a 1D array.

int[][] tickets = { {12, 5, 9}, {7, 3, 10} };
for (int row = 0; row < tickets.length; row++)
{
    for (int col = 0; col < tickets[0].length; col++)
    {
        System.out.print(tickets[row][col] + " ");
    }
    System.out.println();
}

12 5 9
7 3 10

A traversal does not have to print. Any statement that uses grid[row][col] runs once for each element, so the same loops can change every element. Because the code names the actual array location, the change is stored in the array.

int[][] tickets = { {12, 5, 9}, {7, 3, 10} };
for (int row = 0; row < tickets.length; row++)
{
    for (int col = 0; col < tickets[row].length; col++)
    {
        tickets[row][col] += 2;
    }
}
System.out.println(tickets[0][0] + " " + tickets[0][2]);
System.out.println(tickets[1][0] + " " + tickets[1][2]);

14 11
9 12

public class BoundsSwapped
{
    public static void main(String[] args)
    {
        int[][] tickets = { {12, 5, 9}, {7, 3, 10} };
        for (int row = 0; row < tickets[0].length; row++)
        {
            for (int col = 0; col < tickets.length; col++)
            {
                System.out.print(tickets[row][col] + " ");
            }
            System.out.println();
        }
    }
}

12 5
7 3
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2

int[][] temps = { {61, 64}, {58, 70}, {66, 59} };
for (int day = 0; day < temps.length; day++)
{
    System.out.print("Day " + day + ":");
    for (int reading = 0; reading < temps[0].length; reading++)
    {
        System.out.print(" " + temps[day][reading]);
    }
    System.out.println();
}

Day 0: 61 64
Day 1: 58 70
Day 2: 66 59

double[][] prices = new double[4][6];
int visits = 0;
for (int r = 0; r < prices.length; r++)
{
    for (int c = 0; c < prices[0].length; c++)
    {
        visits++;
    }
}
System.out.println(visits);

The theater manager now asks a different question: how did each showtime do across all the days? That means reading the table down each column: every value for showtime 0, then every value for showtime 1, and so on. Row-major order gives you the wrong grouping.

Switching to this order needs only one change: swap which loop is on the outside. If the outer loop picks a column and the inner loop walks down the rows, then the inner loop finishes a whole column before the outer loop moves right to the next one. Visiting a 2D array this way, down each column before moving to the next column, is called column-major order.

Two things do not change. The bounds still belong to their own index: the column loop still uses grid[0].length, and the row loop still uses grid.length. The element is still written grid[row][col], row first, because the first bracket picks the row no matter which loop is on the outside.

(In both rows of the table, each loop stops before reaching the length.)

int[][] tickets = { {12, 5, 9}, {7, 3, 10} };
for (int col = 0; col < tickets[0].length; col++)
{
    for (int row = 0; row < tickets.length; row++)
    {
        System.out.print(tickets[row][col] + " ");
    }
    System.out.println();
}

12 7
5 3
9 10

The same six values come out in both orders; only the sequence differs. Here are both sequences for the ticket table side by side:

int[][] tickets = { {12, 5, 9}, {7, 3, 10} };
for (int col = 0; col < tickets[0].length; col++)
{
    System.out.print("Showtime " + col + ":");
    for (int row = 0; row < tickets.length; row++)
    {
        System.out.print(" " + tickets[row][col]);
    }
    System.out.println();
}

Showtime 0: 12 7
Showtime 1: 5 3
Showtime 2: 9 10

public class IndexesSwapped
{
    public static void main(String[] args)
    {
        int[][] tickets = { {12, 5, 9}, {7, 3, 10} };
        for (int col = 0; col < tickets[0].length; col++)
        {
            for (int row = 0; row < tickets.length; row++)
            {
                System.out.print(tickets[col][row] + " ");
            }
            System.out.println();
        }
    }
}

12 5
7 3
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2

int[][] tickets = { {12, 5, 9}, {7, 3, 10} };
for (int col = 0; col < tickets[0].length; col++)
{
    for (int row = 0; row < tickets.length; row++)
    {
        System.out.print(tickets[row][col] + " ");
    }
    System.out.println();
}

String[][] letters = { {"c", "a", "t"}, {"o", "w", "l"} };
for (int c = 0; c < letters[0].length; c++)
{
    for (int r = 0; r < letters.length; r++)
    {
        System.out.print(letters[r][c]);
    }
}
System.out.println();

coawtl

int[][] grid = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} };
for (int c = 0; c < grid[0].length; c++)
{
    for (int r = 0; r < grid.length; r++)
    {
        if (r == 1)
        {
            System.out.print(grid[r][c] + " ");
        }
    }
}
System.out.println();

Row-major and column-major are the two standard orders, but they are not the only ones. A program might need the most recent day first, or just one day, or just one showtime. In every case, the order of the visits is decided by three things you control: which loop is outside, where each loop starts, and which way it counts. This is the same control you had over a single loop in Topic 2.8, now used twice.

To go backward through the rows, start at the last row index and count down to 0. The last valid index is one less than the length, so the last row is grid.length - 1 and the last column is grid[0].length - 1. The condition becomes >= 0 so that index 0 is still visited.

int[][] tickets = { {12, 5, 9}, {7, 3, 10} };
for (int row = tickets.length - 1; row >= 0; row--)
{
    for (int col = tickets[0].length - 1; col >= 0; col--)
    {
        System.out.print(tickets[row][col] + " ");
    }
    System.out.println();
}

10 3 7
9 5 12

You can also visit only part of the grid. A single row is a 1D array, so one loop across the columns with the row index held fixed visits just that row. A single column needs one loop down the rows with the column index held fixed. No nested loop is needed, because only one index changes.

int[][] tickets = { {12, 5, 9}, {7, 3, 10} };
System.out.print("Day 1:");
for (int col = 0; col < tickets[0].length; col++)
{
    System.out.print(" " + tickets[1][col]);
}
System.out.println();
System.out.print("Showtime 2:");
for (int row = 0; row < tickets.length; row++)
{
    System.out.print(" " + tickets[row][2]);
}
System.out.println();

Day 1: 7 3 10
Showtime 2: 9 10

public class BackwardOffByOne
{
    public static void main(String[] args)
    {
        int[][] tickets = { {12, 5, 9}, {7, 3, 10} };
        for (int row = tickets.length; row >= 0; row--)
        {
            for (int col = tickets[0].length - 1; col >= 0; col--)
            {
                System.out.print(tickets[row][col] + " ");
            }
            System.out.println();
        }
    }
}

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2

int[][] grid = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
for (int c = grid[0].length - 1; c >= 0; c--)
{
    for (int r = 0; r < grid.length; r++)
    {
        System.out.print(grid[r][c]);
    }
    System.out.println();
}

369
258
147

int[][] grid = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
for (int k = 0; k < grid.length; k++)
{
    System.out.print(grid[k][grid.length - 1 - k] + " ");
}
System.out.println();

Indexed loops give you full control, but when you just want every element in order and do not care about positions, all the index bookkeeping (row < grid.length, grid[row][col]) is extra work and extra places to make a mistake. For a 1D array, Topic 4.4 gave you a shortcut: the enhanced for loop, which hands you each element in turn with no index at all. A 2D array can use it too.

The key is the fact from Topic 4.11: a 2D array is an array of arrays. If an enhanced for loop goes through the outer array, each element it hands you is not a number; it is a whole row, which is a 1D array. So the outer loop variable must have the type of a row. For an int[][], that type is int[]. Then a second enhanced for loop can go through that row, and each element it hands you is a single int.

A nested enhanced for loop is an enhanced for loop inside the body of another enhanced for loop. For a 2D array, the outer loop goes through the rows and the inner loop goes through the elements of one row.

for (int[] row : grid)
{
    for (int value : row)
    {
        // use value
    }
}

• int[] row: the outer variable’s type is one row of grid. It drops one pair of brackets from int[][].
• : grid: the outer loop goes through the outer array, so it gets one row at a time.
• int value: the inner variable’s type is the element type of the row, int. It drops the last pair of brackets.
• : row: the inner loop goes through the current row, not through grid.

Because the outer loop always goes through the rows from first to last, and the inner loop always goes across a row from first to last, a nested enhanced for loop always visits in row-major order. It cannot go column by column or backward; for those orders you need indexed loops.

int[][] tickets = { {12, 5, 9}, {7, 3, 10} };
for (int[] day : tickets)
{
    for (int count : day)
    {
        System.out.print(count + " ");
    }
    System.out.println();
}

12 5 9
7 3 10

The same shape works for any element type. Only the types in the headers change: for a String[][], a row is a String[] and an element is a String.

String[][] seats = { {"Ana", "Ben"}, {"Cy", "Dee"}, {"Eli", "Fay"} };
for (String[] row : seats)
{
    for (String name : row)
    {
        System.out.print(name.substring(0, 1));
    }
    System.out.print("/");
}
System.out.println();

AB/CD/EF/

public class OuterTypeWrong
{
    public static void main(String[] args)
    {
        int[][] tickets = { {12, 5, 9}, {7, 3, 10} };
        for (int day : tickets)
        {
            System.out.println(day);
        }
    }
}

OuterTypeWrong.java:6: error: incompatible types: int[] cannot be converted to int

double[][] times = { {9.5, 8.75}, {10.0, 7.25} };
for (double[] lane : times)
{
    for (double t : lane)
    {
        System.out.print(t + " ");
    }
    System.out.println();
}

9.5 8.75
10.0 7.25

Back to the theater: the manager wants to add 2 tickets to every entry. In 4.12.1 indexed loops did this. The enhanced for loop looks shorter, so it is tempting to use it here too. Will it work?

Recall the rule for 1D arrays from Topic 4.4: an enhanced for loop variable holds a copy of the current element. Assigning a new value to that variable changes the copy and leaves the array alone. The same rule holds for the inner variable of a nested enhanced for loop, because that variable holds a copy of one int.

int[][] tickets = { {12, 5, 9}, {7, 3, 10} };
for (int[] day : tickets)
{
    for (int count : day)
    {
        count += 2;
    }
}
System.out.println(tickets[0][0] + " " + tickets[1][2]);

12 10

What about the outer variable? It works differently, and the difference explains a lot about arrays of arrays. A row is an array, which is an object, so the 2D array does not store the row itself; it stores a reference to it. The outer variable day gets a copy of that reference, which points to the very same row array that tickets points to. This is the reference sharing from Topic 3.6: two references to one object. So if you change an element through day, using day[col], you change the real row.

int[][] tickets = { {12, 5, 9}, {7, 3, 10} };
for (int[] day : tickets)
{
    for (int col = 0; col < day.length; col++)
    {
        day[col] += 2;
    }
}
System.out.println(tickets[0][0] + " " + tickets[1][2]);

14 12

public class ValueAsIndex
{
    public static void main(String[] args)
    {
        int[][] tickets = { {12, 5, 9}, {7, 3, 10} };
        for (int[] day : tickets)
        {
            for (int count : day)
            {
                System.out.println(day[count]);
            }
        }
    }
}

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 12 out of bounds for length 3

// I
for (int[] row : grid)
{
    for (int value : row)
    {
        value += 1;
    }
}

// II
for (int r = 0; r < grid.length; r++)
{
    for (int c = 0; c < grid[0].length; c++)
    {
        grid[r][c] += 1;
    }
}

// III
for (int[] row : grid)
{
    for (int c = 0; c < row.length; c++)
    {
        row[c] += 1;
    }
}

A school garden is planted in beds, recorded as a 2D array of plant names with "-" for an empty spot. The program below fills every empty spot with beans, then prints the garden two ways. It uses three traversals: an indexed row-major traversal to change elements, a nested enhanced for loop to print by row, and an indexed column-major traversal to print by column.

public class GardenGrid
{
    public static void main(String[] args)
    {
        String[][] garden = { {"kale", "-", "corn"}, {"-", "peas", "-"} };

        for (int row = 0; row < garden.length; row++)
        {
            for (int col = 0; col < garden[0].length; col++)
            {
                if (garden[row][col].equals("-"))
                {
                    garden[row][col] = "beans";
                }
            }
        }

        System.out.println("By row:");
        for (String[] bed : garden)
        {
            for (String plant : bed)
            {
                System.out.print(plant + " ");
            }
            System.out.println();
        }

        System.out.println("By column:");
        for (int col = 0; col < garden[0].length; col++)
        {
            System.out.print("Column " + col + ":");
            for (int row = 0; row < garden.length; row++)
            {
                System.out.print(" " + garden[row][col]);
            }
            System.out.println();
        }
    }
}

By row:
kale beans corn
beans peas beans
By column:
Column 0: kale beans
Column 1: beans peas
Column 2: corn beans

• Traversing a 2D array takes nested loops. Each loop variable goes from 0 to one less than its length: grid.length for rows and grid[0].length for columns.
• In row-major order the outer loop goes through the rows and the inner loop across each row. In column-major order the outer loop goes through the columns and the inner loop down each column. Either way the element is grid[row][col], row first.
• By choosing which loop is outside, where each loop starts, and which way it counts, you can visit in other orders, such as backward, or just one row or column with a single loop.
• In a nested enhanced for loop, the outer variable is a row, with a 1D array type such as int[], and the inner variable is an element of that row. It always visits in row-major order.
• Assigning to an enhanced for loop variable does not change the array. To change elements, assign through an index, such as grid[row][col] or row[col].
• Swapped bounds, swapped indexes, and starting a backward loop at the length all ask for an index that does not exist and throw an ArrayIndexOutOfBoundsException.

int[][] grid = { {5, 1, 8}, {2, 7, 4}, {9, 3, 6} };
for (int r = 0; r < grid.length; r++)
{
    if (r % 2 == 0)
    {
        for (int c = 0; c < grid[0].length; c++)
        {
            System.out.print(grid[r][c] + " ");
        }
    }
    else
    {
        for (int c = grid[0].length - 1; c >= 0; c--)
        {
            System.out.print(grid[r][c] + " ");
        }
    }
}
System.out.println();

5 1 8 4 7 2 9 3 6

int[][] table = new int[2][3];
for (int r = 0; r < table.length; r++)
{
    for (int c = 0; c < table[0].length; c++)
    {
        table[r][c] = r * 10 + c;
    }
}
for (int c = 0; c < table[0].length; c++)
{
    for (int r = 0; r < table.length; r++)
    {
        System.out.print(table[r][c] + " ");
    }
    System.out.println();
}

0 10
1 11
2 12

public class InnerTypeWrong
{
    public static void main(String[] args)
    {
        String[][] words = { {"to", "be"}, {"or", "not"} };
        for (String[] row : words)
        {
            for (String[] word : row)
            {
                System.out.print(word + " ");
            }
        }
        System.out.println();
    }
}

InnerTypeWrong.java:8: error: incompatible types: String cannot be converted to String[]

String[][] words = { {"to", "be"}, {"or", "not"} };
for (String[] row : words)
{
    for (String word : row)
    {
        System.out.print(word + " ");
    }
}
System.out.println();

int[][] grid = { {4, 1}, {2, 8} };
for (int[] row : grid)
{
    for (int value : row)
    {
        value = 0;
    }
    row[0] = 9;
}
System.out.println(grid[0][0] + " " + grid[0][1] + " " + grid[1][0] + " " + grid[1][1]);

• I can write the loop headers for a row-major traversal and say which length bounds each loop. Reread
• I can trace a row-major traversal and explain why swapped bounds throw an exception. Reread
• I can change a row-major traversal into a column-major one and still write grid[row][col]. Reread
• I can trace a traversal that counts backward, or that visits only one row or one column. Reread
• I can write the types of both variables in a nested enhanced for loop and say what order it visits. Reread
• I can explain why assigning to an enhanced for loop variable does not change the array, and which loops do. Reread