AP Computer Science A · Unit 4 lecture · Part 10 of 14 · 9 min

4.13 Implementing 2D array algorithms2D algorithms: rows, columns and neighbors

Mr. Thompkins
Everything in the 1D toolbox works on a 2D array. The only new question is: on what? One row, one column, the whole grid, or the cells around a cell.

To work on each row separately, reset your sum or counter inside the outer loop, at the start of each row. To work on one column, hold c fixed and let only r move. To work on the whole grid, keep one variable outside both loops.

1public static int[] rowTotals(int[][] g)2{3    int[] totals = new int[g.length];14    for (int r = 0; r < g.length; r++)5    {6        for (int c = 0; c < g[r].length; c++)7        {8            totals[r] += g[r][c];29        }10    }11    return totals;12}1314public static int colMax(int[][] g, int c)15{316    int best = g[0][c];317    for (int r = 1; r < g.length; r++)18    {19        if (g[r][c] > best)20        {21            best = g[r][c];22        }23    }24    return best;25}
  1. line 3 One total per row, all starting at 0
  2. line 8 Each row adds into its own slot
  3. line 15-16 One column: c stays fixed and only r moves
output › rowTotals(heat) is {14, 25, 15}; colMax(heat, 1) is 7
A total for every row, and the largest value in one column.
?Wait, why doesn't rowTotals set each totals[r] to 0 first?
new int[g.length] already fills the array with 0s, the default for int. So totals[r] += g[r][c] starts from 0 for every row automatically.

Neighbor questions look at the cells next to a cell: above, below, left and right. The danger is the edge. A cell in row 0 has nothing above it, so before you read g[r - 1][c], check that r > 0. Do the same for every direction.

1public static int neighborSum(int[][] g, int r, int c)2{3    int sum = 0;4    if (r > 0)15    {6        sum += g[r - 1][c];7    }8    if (r < g.length - 1)19    {10        sum += g[r + 1][c];11    }12    if (c > 0)213    {14        sum += g[r][c - 1];15    }16    if (c < g[0].length - 1)217    {18        sum += g[r][c + 1];19    }20    return sum;21}
  1. line 4-8 Is there a row above? a row below?
  2. line 12-16 Is there a column to the left? to the right?
output › neighborSum(heat, 1, 2) is 14; neighborSum(heat, 0, 0) is 16
Add up the neighbors that exist.
274193856027274193856027cell (1, 2): 4 neighborscorner (0, 0): only 24 + 2 + 3 + 5 = 149 + 7 = 16check the edge before you look past it
An inside cell has 4 neighbors. A corner has only 2.

Because each row is a reference, you can rearrange whole rows without touching their elements: the three-line swap works on rows too, with an int[] temporary.

Pause and think
Starting from the original heat array, what are heat[0][0] and heat[2][0] after int[] tmp = heat[0]; heat[0] = heat[2]; heat[2] = tmp;?
I thought about it. Show me
6 and 2. The swap exchanges the references to rows 0 and 2, so heat[0] is now {6, 0, 2, 7} and heat[2] is {2, 7, 4, 1}.
?Wait, what does the ! do in !lot[r][c]?
! means "not". lot[r][c] is a boolean, so !lot[r][c] is true when the spot is empty (false). It's the same as writing lot[r][c] == false.
Write the method
A parking lot is a boolean[][] where true means a space is taken. Write firstFullRow(boolean[][] lot), which returns the index of the first row whose spaces are all taken, or -1 if no row is full.
1public static int firstFullRow(boolean[][] lot)2{3    for (int r = 0; r < lot.length; r++)4    {5        boolean full = true;16        for (int c = 0; c < lot[r].length; c++)7        {8            if (!lot[r][c])29            {10                full = false;211            }12        }13        if (full)314        {15            return r;316        }17    }18    return -1;419}
  1. line 5 Reset the flag at the start of every row
  2. line 8-10 One empty spot means this row is not full
  3. line 13-15 Decide after the whole row is checked
  4. line 18 Only after every row: no full row
output › for { {true, false, true}, {true, true, true}, {false, true, true} } it returns 1
  1. Rows on the outside, because the answer is a row: for (int r = 0; r < lot.length; r++).
  2. For each row, start by assuming it's full: boolean full = true; inside the outer loop.
    Why?
    Reset per row. If full were declared once before the loops, one empty space in row 0 would mark every later row as not full.
  3. Check every space in the row: for (int c = 0; c < lot[r].length; c++) { if (!lot[r][c]) { full = false; } }
  4. After the inner loop, decide: if (full) { return r; }
    Why?
    The return must wait until the whole row is checked.
  5. After both loops, return -1;. For { {true, false, true}, {true, true, true}, {false, true, true} } the method returns 1.

Answer: Loop over rows; set full = true per row; any false space sets full = false; after the row, return r if full; after all rows, return -1.

Stuck? Get a hint
  1. What kind of answer is it: a row, a column or a cell?
  2. Where should the "is this row full?" flag be reset?
  3. Where does return -1 go?
Check yourself
What is printed?
int[][] m = { {3, 8}, {7, 1}, {4, 6} };
int r0 = 0;
int c0 = 0;
for (int r = 0; r < m.length; r++)
{
    for (int c = 0; c < m[0].length; c++)
    {
        if (m[r][c] > m[r0][c0])
        {
            r0 = r;
            c0 = c;
        }
    }
}
System.out.println(r0 + " " + c0);
  1. A0 1
  2. B1 0
  3. C8
  4. D2 1
Show the answer

A. The code tracks the position of the largest value. 8 is largest, at row 0, column 1, and nothing later is bigger, so it prints 0 1. The second choice is the trap: it swaps row and column. The third prints the value, but the code prints positions.

Exam tip from Mr. T

FRQ 4 is the 2D Array question, worth 6 points. Expect points for traversing the right rows and columns without going out of bounds, for the condition, for resetting per-row or per-column values in the right place, and for returning the right thing after the loops. Say each loop bound out loud: rows from g.length, columns from g[0].length.

  • Per-row work: reset inside the outer loop. One column: fix c, move r. Whole grid: one variable outside both loops.
  • Check the edges before reading a neighbor: r > 0, r < g.length - 1, c > 0, c < g[0].length - 1.
  • Rows are references: you can swap or pass whole rows.
  • Decide about a row after its inner loop ends, and return "not found" after all the loops.