4.13 Implementing 2D Array Algorithms

4.13 Implementing 2D Array Algorithms

A two-dimensional array algorithm turns a grid of values into a useful result: a seating chart becomes an occupancy report, a map becomes a terrain analysis, and a matrix of temperatures becomes a search for the hottest region. The essential question is not merely how to visit every element, but what computation should happen at each position and how should neighboring positions be related?

Learning Objective 4.13.A: Develop and implement algorithms that use two-dimensional arrays to solve problems.

Essential Knowledge 4.13.A.1: Algorithms that process two-dimensional arrays commonly use nested iteration, with one loop controlling rows and another controlling columns.

Essential Knowledge 4.13.A.2: The algorithm must use the correct row and column bounds for the particular array; a two-dimensional array may be rectangular rather than square.

The grid-to-result pattern

Most 2D array algorithms follow a three-part pattern:

1. Visit each required element.
2. Process the current element, often using an accumulator, counter, or comparison.
3. Return or report the result after the traversal finishes.

A useful mental model is a person reading a spreadsheet: move across every column in the first row, then return to the first column and move across the second row, continuing until all rows have been processed.

The outer loop normally selects a row, while the inner loop selects a column within that row. For an array named grid, the current element is grid[row][column].

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

Worked example: total rainfall

Suppose rainfall stores daily rainfall measurements for several weather stations. Each row represents one station, and each column represents one day. To calculate the total rainfall, initialize an accumulator before the loops, add each element exactly once, and return the accumulator afterward.

public static double totalRainfall(double[][] rainfall) {
    double total = 0.0;

    for (int row = 0; row < rainfall.length; row++) {
        for (int day = 0; day < rainfall[row].length; day++) {
            total += rainfall[row][day];
        }
    }

    return total;
}

For the grid below,

$$ \begin{bmatrix} 1.2 & 0.0 & 2.5 \ 3.1 & 1.4 & 0.8 \end{bmatrix} $$

the algorithm adds $1.2 + 0.0 + 2.5 + 3.1 + 1.4 + 0.8$, producing $9.0$. Notice that rainfall.length is the number of rows, while rainfall[row].length is the number of columns in the current row.

Algorithms beyond simple accumulation

The same traversal structure can support many operations:

Goal	State to maintain	Update rule
Count values above a threshold	count	Increment when the current value qualifies
Find the largest value	maximum	Replace when the current value is larger
Compute a row total	rowTotal	Reset for each row, then add across columns
Change every element	No accumulator required	Assign a transformed value to each position

For example, counting seats marked "open" requires a comparison at each location:

public static int countOpenSeats(String[][] seats) {
    int count = 0;

    for (int row = 0; row < seats.length; row++) {
        for (int column = 0; column < seats[row].length; column++) {
            if (seats[row][column].equals("open")) {
                count++;
            }
        }
    }

    return count;
}

Common misconception: every 2D array is square

A frequent error is using grid.length for both loop bounds. That works only when the number of rows happens to equal the number of columns. In Java, a 2D array is an array of row arrays, so different rows can even have different lengths; grid[row].length is therefore the safest column bound.

Another error is initializing a value at the wrong level. A total for the entire grid is initialized before the outer loop, but a total for each row must be reset inside the outer loop and before the inner loop begins.

AP skills in action

This topic most directly develops Computational Thinking Practice 1 — Design Code, when selecting the state and traversal needed; Computational Thinking Practice 2 — Develop Code, when implementing nested loops and updates; and Computational Thinking Practice 3 — Analyze Code, when tracing indices, testing boundary cases, and debugging incorrect results. Computational Thinking Practice 4 — Document Code and Computing Systems applies when comments clarify what each index represents, while Computational Thinking Practice 5 — Use Computers Responsibly matters when grid data represents people, locations, or other sensitive information.

Retrieval check

A rectangular array has $4$ rows, and row $2$ has $7$ elements. What expressions give the number of rows and the number of columns in row $2$? Why would using array[0].length be less robust than using array[2].length?

Answer: The number of rows is array.length, and the number of columns in row $2$ is array[2].length. The row-specific expression correctly handles arrays whose rows have different lengths.