Matrix Traversal Pattern

Why this pattern matters for LeetCode

Grid problems look unfamiliar until you realize the grid is just a graph where each cell is a node and edges connect it to its four (or eight) neighbors. Once you see that, every graph algorithm applies: DFS to explore a connected region, BFS to find the shortest path. The only additions are boundary checks (don't go off the grid) and visited marking (don't revisit cells).

What the Matrix Traversal pattern is

Matrix traversal applies BFS or DFS to a 2D grid. Each cell (r, c) has up to four neighbors: (r-1,c), (r+1,c), (r,c-1), (r,c+1). The algorithm visits unvisited cells that satisfy some condition (e.g., are land, not a wall) and marks them visited to prevent re-entry. DFS uses the call stack (or an explicit stack); BFS uses a queue and guarantees shortest-path distances. The key implementation details are the bounds check and the visited guard.

Reach for Matrix Traversal when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Matrix Traversal

• ✓Number of Islands — DFS/BFS from each unvisited land cell to mark the whole island
• ✓Max Area of Island — DFS that returns the count of cells in each island
• ✓Flood Fill — BFS/DFS to repaint a connected region with a new color
• ✓Shortest path in a grid — BFS from source, each step is distance +1
• ✓Pacific Atlantic Water Flow — multi-source BFS from both borders

When NOT to use Matrix Traversal

• ✕The input is a 1D array or linked list — use simpler traversal patterns
• ✕Cells are only connected diagonally — adjust to 8-directional neighbors
• ✕The grid is very large and BFS memory is a concern — iterative DFS may use less space
• ✕The problem is about the values in specific cells, not about connectivity

Better alternative: For non-grid graphs use standard BFS/DFS with an adjacency list. For simple row/column scans without connectivity, a nested loop without visited tracking suffices.

JavaScript code template

Number of Islands — DFS approach, O(n × m) time and space

function numIslands(grid) {
  let count = 0;

  function dfs(r, c) {
    // Out of bounds or not land — stop
    if (r < 0 || r >= grid.length) return;
    if (c < 0 || c >= grid[0].length) return;
    if (grid[r][c] !== '1') return;

    grid[r][c] = '0'; // mark visited by overwriting (no extra space)

    dfs(r - 1, c);
    dfs(r + 1, c);
    dfs(r, c - 1);
    dfs(r, c + 1);
  }

  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === '1') {
        dfs(r, c); // explore and sink the whole island
        count++;
      }
    }
  }

  return count;
}

The outer nested loop finds unvisited land cells. Each call to dfs sinks the entire connected island by overwriting '1' with '0'. After dfs returns, every cell in that island is marked so the outer loop won't revisit it. count++ once per island entry. Total work: each cell is visited at most once — O(n × m).

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Identify the starting condition — which cells trigger an exploration (unvisited land, a '1', a color match, etc.).
2. 2Write the DFS/BFS function with a bounds check first: return immediately if (r, c) is out of the grid.
3. 3Write the visited check: return if the cell doesn't satisfy the condition or is already marked visited.
4. 4Mark the current cell visited before exploring neighbors (prevents revisiting on backtrack).
5. 5Recurse into all 4 neighbors (or enqueue them for BFS).
6. 6In the main function, loop over every cell; start a new DFS/BFS from each unvisited trigger cell and count.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Flood Fill

  DFS from the starting cell to repaint all connected same-color cells — the simplest grid DFS.

  Premium→
• Number of Islands

  Count how many times a fresh DFS is triggered — each trigger is a new island.

  Premium→
• Max Area of Island

  DFS returns the cell count of each island; track the maximum across all islands.

  Premium→

Coming soon

• Rotting Oranges

  Multi-source BFS from all rotten oranges simultaneously — the level count is the minimum minutes to rot all.

  Coming soon

Common mistakes beginners make

• ✕Checking bounds after accessing grid[r][c] — this causes an out-of-bounds error. Always check r and c are in range before accessing the cell.
• ✕Not marking visited before recursing — the function will loop between two adjacent cells forever.
• ✕Using DFS when shortest path is needed — DFS finds any path, not the shortest. Use BFS for minimum-distance problems.
• ✕Modifying the input grid without checking if mutation is allowed — overwriting to mark visited is common but ask the interviewer; if not allowed, use a separate visited boolean array.

DFS vs BFS for Matrix Traversal

Choose the right tool for the job.

Time and space complexity

Each cell is visited at most once — the visited mark (overwriting or a boolean array) prevents re-entry. The outer loop visits all n×m cells once. Each DFS/BFS call processes one cell and enqueues/recurses at most 4 neighbors. Total: O(n×m) time. Space: DFS call stack or BFS queue can hold at most O(n×m) cells in the worst case (the whole grid is one island).

Frequently asked questions

Why does the bounds check come before the visited check?

Accessing grid[r][c] when r or c is out of range throws an error before you can check the value. The order must be: bounds first, then value/visited check. A common pattern: write a helper `inBounds(r, c)` that returns false immediately for out-of-range indices.

When should I use BFS instead of DFS for grid problems?

Use BFS when you need the minimum number of steps to reach something. BFS expands cells in order of distance from the source — the first time it reaches a cell, that's the shortest path. DFS explores as deep as possible first and may reach a cell via a longer path.

Should I overwrite the grid to mark visited or use a separate array?

Overwriting is more space-efficient (O(1) extra) and common in interviews. But it mutates the input. If the problem says don't modify the input, or if you need the original values later, allocate a separate `visited` boolean array of the same dimensions.

How do I handle diagonal neighbors (8-directional)?

Define a directions array of all 8 offsets: [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]. Loop over it to generate all 8 neighbors instead of hardcoding 4 calls. The rest of the algorithm is identical.