4.13 Implementing 2D Array Algorithms

What you need to know

• Named algorithms: sum/max/min of the whole grid, of a row, or of a column; count cells meeting a condition; find a value's position; check whether every element in a row/column meets a condition; find rows/columns with a property.
• Row operations: a method that takes int[] can be called with grid[r]. Reusing a 1D helper is common in FRQ 4.
• Column operations: there's no direct column array; loop over r with fixed c.
• Building a 2D array from a 1D array or list: fill in row-major (or column-major, if specified) order using a running index into the source.
• Searching: nested loops; return as soon as found (a return exits both loops).
• Modifying in place: nested loops with standard indices, assigning to grid[r][c].

Worked example

// FRQ 4-style: return the index of the row with the largest sum
public static int maxRow(int[][] g)
{
    int best = 0;
    int bestSum = rowSum(g[0]);
    for (int r = 1; r < g.length; r++)
    {
        int s = rowSum(g[r]);
        if (s > bestSum)
        {
            bestSum = s;
            best = r;
        }
    }
    return best;
}
public static int rowSum(int[] row)
{
    int sum = 0;
    for (int v : row) sum += v;
    return sum;
}

// fill a 2D array from a 1D array in row-major order
int k = 0;
for (int r = 0; r < g.length; r++)
{
    for (int c = 0; c < g[0].length; c++)
    {
        g[r][c] = source[k];
        k++;
    }
}

Going deeper

The nuance, edge cases, and connections that turn a 3 into a 5.

• The CED's named 2D algorithms: sum/max/min/count over the whole grid, over a row, or over a column; find a value's location; determine whether a row or column has a property; find the row/column with the largest sum; count occurrences; transform every element.
• Reuse 1D helpers: if you have rowSum(int[] row), then the grid's max-row is a loop over r calling rowSum(g[r]). FRQ 4 part (a) is often the helper; part (b) uses it across the grid. Using your part (a) in part (b) is expected — and if you got (a) wrong, (b) is still graded assuming (a) works.
• Column operations have no helper shortcut — write the loop over r with fixed c inside a loop over c.
• Search with early return: nested loops; return when found exits both. Returning a position needs both indices — FRQ 4 may give you a Location class or ask for a formatted String.
• Filling from a 1D source: running index k; assign g[r][c] = src[k]; k++; in row-major order (or column-major if specified). k goes 0 to R×C−1.
• In-place transformation: nested standard loops with assignment. Enhanced for can't do this for primitives.
• Neighbor checks (is a cell surrounded by…): guard each neighbor's indices with bounds checks. Corners have 3 neighbors, edges 5, interior 8.
• Rubric reality for FRQ 4: points for correct nested loops with correct bounds, correct access g[r][c], correct condition/accumulation, correct return. Get the loop structure right and you've earned most of it.

Mistakes that cost points

• Not reusing part (a). Rewriting it wastes time and invites errors.
• Treating a column like a row. Fixed c, loop r.
• Resetting the running index inside the outer loop. k continues across rows.
• Neighbor access without bounds checks. Exception at the edges.

Practice questions

Written in the style of the real exam. Try each one before revealing the answer.

public static int count(int[][] g)
{
    int c = 0;
    for (int r = 0; r < g.length; r++)
    {
        if (g[r][0] < g[r][1]) c++;
    }
    return c;
}