TOPIC 4.13 · STUDY

Implementing 2D Array Algorithms

Implement 2D array algorithms by choosing which cells to visit. Nest a column loop inside a row loop to touch every cell for a total, min, max, or count. Fix one row and vary the column for a row algorithm, or fix one column and vary the row for a column algorithm.

4.13.A

Implementing 2D array algorithms

A 2D algorithm is just a plan for which cells to read and what to do with each value. The shape of the loops matches the shape of the region. To visit the whole rectangle, nest a column loop inside a row loop and use grid[r][c]. To work on one row only, hold the row index still and vary the column. To work on one column only, hold the column index still and vary the row. Stay with int[][] and ordinary for loops. Do not bring in ArrayList or sorting.

Whole-grid patterns start a running result, then update it for every cell. A total starts at 0 and adds each grid[r][c]. A minimum or maximum starts at one real cell, often grid[0][0], and replaces that seed whenever a smaller or larger value appears. A count starts at 0 and increments only when a test such as grid[r][c] > cutoff succeeds. The same three ideas work on a single row or a single column once you shrink the loop bounds.

int[][] pads = {
    {6, 2, 9},
    {4, 8, 1}
};
int total = 0;
int least = pads[0][0];
int most = pads[0][0];
int tall = 0;
for (int r = 0; r < pads.length; r++) {
    for (int c = 0; c < pads[0].length; c++) {
        total += pads[r][c];
        if (pads[r][c] < least) {
            least = pads[r][c];
        }
        if (pads[r][c] > most) {
            most = pads[r][c];
        }
        if (pads[r][c] > 5) {
            tall++;
        }
    }
}
System.out.print(total + " " + least + " " + most + " " + tall);

The nested loops visit 6, 2, 9, 4, 8, and 1. The total becomes 30. The least value is 1 and the greatest is 9. Three cells are greater than 5, so tall is 3. The printed line is 30 1 9 3. Seeding least and most from pads[0][0] matters: starting at 0 would fail if every cell were positive and larger than 0, or if every cell were negative.

A row algorithm fixes the row and walks the columns. A column algorithm fixes the column and walks the rows. The diagram shades column 1 of a small tray: the values in that strip are the only ones a column loop should read.

A 3-by-3 tray with column 1 shaded. Row indexes sit on the left; column indexes sit above each cell.

Column 1 holds 7, 1, and 8. A column loop keeps c at 1 and changes r from 0 through length - 1.

int[][] tray = {
    {4, 7, 2},
    {9, 1, 5},
    {3, 8, 6}
};
int rowSum = 0;
for (int c = 0; c < tray[1].length; c++) {
    rowSum += tray[1][c];
}
int colMax = tray[0][1];
for (int r = 1; r < tray.length; r++) {
    if (tray[r][1] > colMax) {
        colMax = tray[r][1];
    }
}
int colCount = 0;
for (int r = 0; r < tray.length; r++) {
    if (tray[r][1] > 5) {
        colCount++;
    }
}
System.out.print(rowSum + " " + colMax + " " + colCount);

Row 1 is 9 + 1 + 5, so rowSum is 15. Column 1 holds 7, 1, and 8; the largest is 8, and two of those values are greater than 5, so colCount is 2. The print is 15 8 2. A row min would seed from tray[row][0] and scan the remaining columns. A column min would seed from tray[0][col] and scan the remaining rows. Average follows the same visit pattern: keep a sum, divide by how many cells were visited, and remember that int division truncates.

Key points

  • Whole-grid work nests a column loop inside a row loop and uses grid[r][c].
  • A row algorithm fixes the row index and varies the column.
  • A column algorithm fixes the column index and varies the row.
  • Sum starts at 0; min and max start at a real cell such as grid[0][0] or the first cell of that row or column.
  • Count starts at 0 and increments only when the cell passes the test.
  • No ArrayList and no sorting belong in these algorithms.

A column loop holds the column index still and changes the row.

Practice this topic