1Understand
The idea
A grid is a list of rows: grid[r][c], with 0 <= r < rows and 0 <= c < cols. Most grid problems are careful index bookkeeping: direction vectors for neighbours, shrinking boundaries for spirals, and reversing or transposing for rotations. Check bounds before you index, never after.
Intuition
A grid is a list of rows: grid[r][c] with 0 ≤ r < rows and 0 ≤ c < cols. Most matrix problems are careful index bookkeeping: direction vectors for neighbours, shrinking boundaries for spirals, reverse/transpose for rotations.
Check bounds before you index, never after. For in-place transforms, be explicit about what you still need to read, overwriting too early loses information.
Direction arrays like DIRS = [(0,1),(1,0),(0,-1),(-1,0)] keep neighbour loops uniform.
What you will be able to do
- Handle bounds cleanly
- Transform a matrix in place
When to use it
- Input is a grid or matrix
- Rotate, transpose or spiral order
- Neighbours in 4 or 8 directions
2See it
Walkthrough
Row-major visit
3×3 grid, walk (r, c) with bounds checks.
1 / 5
Start at (0,0). Four directions: up/down/left/right, skip out-of-bounds.
Live template
Line 1 active
Complexity: time O(rows·cols), space O(1) to O(rows·cols)
Visiting every cell is O(rows · cols). Extra space is O(1) beyond the output, unless you mark visited explicitly. In-place rotation/transpose is O(1) extra; building a new matrix is O(rows · cols) space.
Read the walkthrough as text
Spiral order on a 3×3.
1 2 34 5 67 8 9
- Maintain
top, bottom, left, rightboundaries; start at the outer layer. - Walk right across the top row (
1,2,3), then down the right column (6,9), then left (8,7), then up (4). - Shrink the boundaries inward and repeat for the centre
5. - Stop when
top > bottomorleft > right.
Each cell is visited once; the trick is updating bounds after each side and not double-visiting corners.
3Recognise it
Kinds of problems (7)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Neighbour iteration (4 / 8 directions)
Example. Flood fill or count islands in a grid.
How. DIRS = ((1,0),(-1,0),(0,1),(0,-1)); check 0 <= nr < rows and 0 <= nc < cols before visiting.
Spiral order
Example. Return matrix elements in spiral order.
How. Shrink top/bottom/left/right borders; peel one layer per iteration.
Rotate or transpose in place
Example. Rotate image 90° or transpose a square matrix.
How. Layer swaps or i<j transpose; avoid reading cells after you overwrote them.
Diagonal traversal
Example. Anti-diagonals or same-sum diagonals in a matrix.
How. Offset by r+c or r-c bucketing, or zig-zag walk along diagonals.
Row/column markers (set matrix zeroes)
Example. If any cell is 0, zero its whole row and column in place.
How. Use first row/column as flags, then clear in two passes using those markers.
Index arithmetic on a flattened grid
Example. Treat 2-D cell as index i = r*cols + c.
How. Div/mod recover (r, c); same formula avoids nested boundary bugs on border cells.
In-place state encoding (simultaneous updates)
Example. Mark visited or old/new state in the same int cell.
How. Add offset or use high bit for marker; decode after traversal or use modulo when reading.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Out of bounds
Why it happens. An off-by-one in a corner case is easy to miss on one boundary.
How it fails. if nr < rows and nc < cols without checking nr >= 0, negative index wraps in Python and reads wrong cells.
Fix. 0 <= nr < rows and 0 <= nc < cols for all four neighbours.
Rows and columns swapped
Why it happens. “Row” and “column” swap mentally when the grid is square.
How it fails. for c in range(len(grid)): use grid[c][r] with r in range(len(grid[0])), rows and columns swapped.
Fix. rows = len(grid), cols = len(grid[0]); visit grid[r][c] with r in range(rows), c in range(cols).
Overwritten too early
Why it happens. In-place rotation saves memory so you rotate one cell at a time immediately.
How it fails. Rotate 90° by writing new values before reading the four-cell cycle, destroys source cells still needed.
Fix. Layer-by-layer swap in a cycle, or copy to buffer, or mark-then-decode in a second pass.
Encoding left in place
Why it happens. You store old and new state in one cell and forget to strip the marker at the end.
How it fails. Mark visited with +10 and return the grid without mod 10, output still contains encoded values.
Fix. Decode in a final pass (mod or subtract marker), or use a separate seen structure when unsure.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.