Arrays & Hashing

Matrix Traversal

Walking 2-D grids: rows, columns, diagonals, spirals and in-place transforms.

Medium, about 60 minutes to practise.

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

iL
0,0
0,1
0,2
1,0
1,1
1,2
2,0
2,1
2,2
012345678
i → index 0

Start at (0,0). Four directions: up/down/left/right, skip out-of-bounds.

for dr, dc in dirs:

Live template

Line 1 active

1for r in range(rows):
2 for c in range(cols):
3 for dr, dc in DIRS:
4 nr, nc = r + dr, c + dc
5 if 0 <= nr < rows and 0 <= nc < cols: ...

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 3
  • 4 5 6
  • 7 8 9
  1. Maintain top, bottom, left, right boundaries; start at the outer layer.
  2. Walk right across the top row (1,2,3), then down the right column (6,9), then left (8,7), then up (4).
  3. Shrink the boundaries inward and repeat for the centre 5.
  4. Stop when top > bottom or left > 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.

All lessons