Skip to main content

DSAPath18 mincore

Matrix Traversal

Matrix traversal treats a grid as indexed cells or an implicit graph. It powers island counting, flood fill, shortest grid paths, spiral order, and dynamic programming tables.

DifficultyCore
TierTier 2
ModuleGraph Foundations
LanguagesPython

Why This Matters

Many graph questions are disguised as grids. Each cell is a vertex, and valid moves to neighboring cells are edges. Matrix traversal is the bridge between arrays, graphs, and DP tables.

The invariant is cell validity: every queued or recursive cell must be inside bounds, unvisited if required, and satisfy the problem's value condition.

Prerequisite Check

Review Arrays, BFS, and DFS. You should be able to map (row, col) to neighboring cells.

Learning Objectives

By the end, you should be able to:

  • Generate valid four-direction and eight-direction neighbors.
  • Treat a grid as an implicit graph.
  • Count connected components with flood fill.
  • Choose BFS for shortest grid paths and DFS for region exploration.
  • Avoid boundary and mutation bugs.

Core Idea

Represent each cell by (row, col). Generate candidate moves, filter invalid cells, and maintain visited state.

PatternInvariantTypical problem
Flood fillvisited cells belong to the current regionislands, image fill
Grid BFSqueue cells have finalized step distanceshortest maze path
Spiral traversalboundaries shrink after each sidespiral order
DP table traversaldependencies already computedgrid path counts

Visual Model

cell (r,c) neighbors:
  (r-1,c)
(r,c-1) (r,c) (r,c+1)
  (r+1,c)

The graph is implicit: you do not need to build adjacency lists for every cell.

Non-Example or Failure Mode

Recursive DFS on a huge grid can exceed the Python recursion limit. For production-size grids, use an explicit stack or queue.

Another failure mode is marking visited after recursion. Mark before expanding so cycles through neighboring cells cannot revisit the same cell.

Worked Example

Count islands in:

1 1 0
0 1 0
1 0 1

Start at the first unvisited 1, flood fill the top-left component, then continue scanning. The grid has three islands under four-direction connectivity.

LeetCode-Style Problem Patterns

PatternRecognition signalMove
Number of islandsconnected 1 cellsDFS/BFS flood fill
Shortest path in binary matrixminimum moves in gridBFS by distance levels
Rotting orangessimultaneous spreadmulti-source BFS
Spiral matrixvisit boundary layersshrink top/right/bottom/left

Common Mistakes

MistakeCorrection
Swapping rows and columns.Name rows and cols; bounds are different.
Forgetting visited state.Mutate a copy or use a set.
Using DFS for shortest path.Use BFS when all moves have equal cost.
Assuming diagonal adjacency.Check whether the problem says four or eight directions.

Diagnostic Questions

Question typeQuestionAnswer signal
DefinitionHow is a grid a graph?Cells are vertices and valid moves are edges.
Example / non-exampleDoes four-direction island counting connect diagonals?No, unless the problem defines diagonal moves.
ComputationWhat is flood-fill complexity for an m x n grid?O(mn) time and up to O(mn) visited/stack/queue space.
ProofWhy does marking visited before expansion matter?It prevents neighboring cells from re-adding the same cell.
TransferWhen does grid traversal become DP?When each cell depends on previously computed neighbor states rather than arbitrary graph reachability.

Exercises

Beginner:

  • List valid neighbors for the corner and center of a 3 x 3 grid.
  • Count islands by hand under four-direction connectivity.
  • Explain why a grid can be an implicit graph.

Intermediate:

  • Implement shortest path in a binary matrix with BFS.
  • Write spiral-order traversal using shrinking boundaries.

Challenge:

  • Compare DFS flood fill and union-find for dynamic island-counting variants.

Diagram Recommendation

Type: grid-neighbor overlay.

Caption: "Each cell connects to valid neighboring cells under the chosen movement rule."

Purpose: Prevent row/column and diagonal-connectivity mistakes.

Implementation Task

Implement island counting using an explicit stack. Keep the input grid unmodified by storing visited coordinates separately.

Run matrix traversal island count

This cell counts four-direction islands and checks boundary behavior.

Output will appear here.

Next Topics

References