Matrices & Simulation

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   A matrix is rows of equal arrays. Row-major: (r, c) is cell r * cols + c of one long line; back with i / cols and i % cols.

   #1
2. ↯use it when

   Spiral → four walls. Rotate → transpose + reverse. Row/column wipes → markers. "All cells at once" → old vs new. Zigzag → row builders.

   #2
3. { }template

   Neighbours: for (int[] d : DIRS) { int nr = r + d[0], nc = c + d[1]; if (nr >= 0 && nr < m && nc >= 0 && nc < n) … }

   #3
4. { }template

   Two states in a cell: read cell & 1, plan cell |= 2, then cell >>= 1. Markers: matrix[r][0] = 0; matrix[0][c] = 0;

   #4
5. O( )cost

   Every walk here is O(m·n) time. Only the space differs: a copy O(m·n) → flags O(m + n) → markers or spare bits O(1).

   #5
6. !trap

   Writing cells while you still read their old values breaks Game of Life and Set Zeroes. Freeze a copy, or keep old + new in one cell.

   #6
7. !trap

   grid.clone() shares rows. i / rows instead of i / cols. Transposing with c from 0 swaps each pair twice.

   #7
8. !trap

   Spiral: without the top <= bottom and left <= right guards, a single leftover row or column is walked twice.

   #8
9. ✦pro tip

   Draw a 3 × 4 rectangle, not a square. Then test 1 × 1, 1 × n and n × 1 before you say done.

   #9

Shaky on a card? Open the chapter or flip its recall cards.