leetExpert

Module 15 · Matrix / 2D Traversal

Practice

Practice~2 min

How to practice this module

Matrix drills reward naming the traversal: layer-by-layer, spiral, or coordinate flood. Rotate, spiral and set-zeroes are structure problems; search-a-2d and number-of-islands lean on coordinates and flood fill; word-search is DFS along a board path. Done when all six show Solved in the hub.

Problems

Matrix — work them in order; difficulty ascends.

0/6

solved

  1. 1Rotate ImageMediumLayer-by-layer swapsWatch for: Rotate rings inward; stash a corner before overwriting — or transpose then mirror, whichever you can trace
  2. 2Spiral MatrixMediumBoundary walkWatch for: Shrink the four bounds after each edge; stop when the visited count reaches m*n so you never double-print
  3. 3Set Matrix ZeroesMediumFirst row / column markersWatch for: Use the first row and column as flags; the [0][0] corner needs its own boolean or you zero the wrong line
  4. 4Search a 2D MatrixMediumFlattened binary searchWatch for: Index a row-major array with (r*n + c) and rely on the ordering the problem states — a plain 2-D scan forfeits the log
  5. 5Number of IslandsMediumGrid flood fillWatch for: Mark visited in place when you land; BFS or DFS from each unvisited '1' and count the frontiers
  6. 6Word SearchMediumDFS path searchWatch for: Restore the board mark after backtracking; check bounds before indexing, not after the deref

Cheatsheet

Matrix — Grids are graphs — boundaries, directions, and in-place layers.

Smell → pattern

  • Visit every cell onceDFS / BFS on grid
  • Rotate / spiral layersLayer peel
  • Set zeroes / mark rowsSentinel row/col

Patterns

4-direction flood

Core

Smell: Islands, regions, connected cells

From a cell, try U/D/L/R inside bounds. Mark visited in-place or with a set. Islands and regions share this skeleton.

Layer / ring walk

Safe

Smell: Rotate, spiral, or peel borders

Process the matrix as concentric rectangles. Corners are the off-by-one hotspot.

First row/col markers

Careful

Smell: O(1) space row/col flags

Reuse the matrix border as boolean flags when O(1) space is required — carefully preserve the corner bit.

Complexity targets

  • Visit all cells

    Time
    O(m·n)
    Space
    O(m·n)*
    Note
    *or O(1) with in-place marks

  • Layer rotate

    Time
    O(m·n)
    Space
    O(1)
    Note
    In-place swaps

Traps

  • Out-of-bounds neighbours

    Always check 0 ≤ nr < m and 0 ≤ nc < n before indexing. Diagonals are optional — don’t add them by habit.

  • Corner flag collision

    matrix[0][0] often dual-purposes row-0 and col-0 marks. Use a separate boolean for one of them or you zero the wrong line.