Skip to content

029 — Matrix Traversal

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

29 — Matrix Traversal

🍽️ Intuition

The Arrays and Strings chapter covered the data structure itself — an indexable sequence, extended here into a grid: [[Int]], a 2-D array. This chapter is about recognizing when to treat that grid as a graph in disguise: every cell is a node, and its up/down/left/right neighbors are its edges.

Picture a firefighter's flood-and-spread strategy when mopping up a wildfire on a grid map of terrain tiles. They start at one burning tile, and the fire spreads to any neighboring tile — north, south, east, or west — that's flammable and not already burnt. Each newly caught tile becomes a new starting point for spreading further, and a tile is only ever marked "burnt" once, so the fire never doubles back on itself or loops forever. Whether the crew tracks this with a wave that expands outward layer by layer, or by chasing one direction all the way to its end before backtracking, the mechanic is the same: start somewhere on the grid, look at the neighbors, only step onto ones that are valid and unvisited, mark them visited, and repeat. That's matrix traversal — treating a 2-D grid as a graph where every cell is a node and its up/down/left/right neighbors are its edges.

🚩 Recognition Signal

Reach for matrix traversal when you see:

  • "Number of islands" or any "count the connected regions" question on a grid of 0s/1s (or land/water, or two colors) — the classic signature of this pattern.
  • "Flood fill" — explicitly starting from one cell and changing every reachable same-valued neighbor, exactly like a paint bucket tool.
  • "Connected region" / "surrounded region" phrasing on a 2-D grid — "capture all regions surrounded by X," "rotting oranges spreading to adjacent fresh ones over time" (this variant wants BFS specifically, since it's asking about spread over discrete time steps/layers).
  • Explicit mention of 4-directional or 8-directional movement on a grid — "you may move up, down, left, or right" (orthogonal) versus "including diagonals" (8-directional) tells you exactly which neighbor-offset list to use.

The unifying tell: the input is a 2-D grid, and the question is about regions, connectivity, or reachability between cells — solved by treating each cell as a graph node and applying DFS or BFS with a visited grid to avoid revisiting cells.

📊 ASCII Diagram

Flood fill spreading from a starting cell, visiting only orthogonal neighbors that are still unvisited land:

grid (1 = land, 0 = water):        visited spread, step by step from (1,1):

1 1 0 0                            1 1 0 0
1 1 0 0                            1 1 0 0
0 0 1 0                            0 0 . 0
0 0 0 1                            0 0 0 .

start (1,1) -> visit (1,1)
  check neighbors: (0,1) land, (2,1) water, (1,0) land, (1,2) water
  visit (0,1) and (1,0), queue/stack them for their own neighbor checks
  (0,1)'s neighbors: (0,0) land -> visit
  (1,0)'s neighbors: (0,0) already visited, (2,0) water -> skip

result: island of size 4 found — {(0,0),(0,1),(1,0),(1,1)}
the (2,2)/(3,3) land cell is a SEPARATE island (no orthogonal path connects them)

💻 Generic Swift Template

func matrixTraversalTemplate(_ grid: [[Int]]) -> Int {
    guard !grid.isEmpty, !grid[0].isEmpty else { return 0 }

    let rows = grid.count
    let cols = grid[0].count
    var visited = Array(repeating: Array(repeating: false, count: cols), count: rows)
    let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]   // 🔧 Fill in: add diagonals if 8-directional

    func isValid(_ r: Int, _ c: Int) -> Bool {
        return r >= 0 && r < rows && c >= 0 && c < cols
            && !visited[r][c]
            && grid[r][c] == 1   // 🔧 Fill in: the actual "can we step here" condition
    }

    func dfs(_ r: Int, _ c: Int) {
        visited[r][c] = true
        // 🔧 Fill in: do whatever per-cell work the problem needs here

        for (dr, dc) in directions {
            let nr = r + dr, nc = c + dc
            if isValid(nr, nc) {
                dfs(nr, nc)
            }
        }
    }

    var regionCount = 0
    for r in 0..<rows {
        for c in 0..<cols {
            if grid[r][c] == 1 && !visited[r][c] {
                dfs(r, c)
                regionCount += 1   // 🔧 Fill in: whatever "found a new region" means for this problem
            }
        }
    }

    return regionCount   // 🔧 Fill in: return whatever the problem actually asks for
}

🧩 Worked Example

Number of Islands — given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands (land connected 4-directionally).

func numIslands(_ grid: [[Character]]) -> Int {
    guard !grid.isEmpty, !grid[0].isEmpty else { return 0 }

    var grid = grid   // mutable local copy — reuse it as the visited tracker
    let rows = grid.count
    let cols = grid[0].count
    let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    func isValid(_ r: Int, _ c: Int) -> Bool {
        return r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] == "1"
    }

    func dfs(_ r: Int, _ c: Int) {
        grid[r][c] = "0"   // mark visited by "sinking" the land — avoids a separate visited grid

        for (dr, dc) in directions {
            let nr = r + dr, nc = c + dc
            if isValid(nr, nc) {
                dfs(nr, nc)
            }
        }
    }

    var islandCount = 0
    for r in 0..<rows {
        for c in 0..<cols {
            if grid[r][c] == "1" {
                dfs(r, c)
                islandCount += 1
            }
        }
    }

    return islandCount
}

// smoke test
let grid1: [[Character]] = [
    ["1","1","1","1","0"],
    ["1","1","0","1","0"],
    ["1","1","0","0","0"],
    ["0","0","0","0","0"]
]
print(numIslands(grid1))   // 1

let grid2: [[Character]] = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
]
print(numIslands(grid2))   // 3

This is the template with one small optimization: instead of a separate visited grid, the DFS "sinks" each visited land cell by overwriting it to "0" in place, so isValid's grid[r][c] == "1" check doubles as the visited check. The outer double loop is unchanged — scan every cell, and whenever an unvisited "1" is found, that's a brand-new island, so DFS floods the whole connected region (sinking it) and the island counter increments exactly once per region.

🧸 Memory Sentence

Matrix traversal is the wildfire spreading across a terrain grid — start a cell, spread to valid unvisited neighbors, mark each one burnt so it's never revisited, and count how many separate fires you had to start.

✅ Check Your Understanding

"Rotting Oranges" (every minute, a rotten orange rots all 4-directionally adjacent fresh oranges; find the minimum minutes until no fresh orange remains, or -1 if impossible) is also a grid-traversal problem — but why is BFS the right choice here instead of DFS, given that the question is specifically about minutes elapsed?

⬅️ Previous: Greedy · Next: Bit Manipulation Tricks ➡️

Clone this wiki locally