Matrix and Graph Interview Patterns: Island Counting, Shortest Path, and Cycle Detection (2025)

Matrix as a Graph

A 2D matrix is an implicit graph: each cell (r, c) is a node; edges connect adjacent cells (up, down, left, right — 4-directional, or 8-directional including diagonals). You do not need to build an explicit adjacency list. The grid itself encodes the graph. Key operations: BFS for shortest path, DFS for connected components (islands), visited matrix to avoid revisiting cells. Most matrix problems reduce to one of these three patterns.

Pattern 1: Island Counting (DFS/BFS Flood Fill)

Count connected components of 1s in a binary grid (LC 200). DFS approach: iterate over all cells. On encountering an unvisited 1: start DFS, mark all reachable 1s as visited (set to 0 or use a visited set), increment count.

def num_islands(grid):
    m, n = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r = m or c = n or grid[r][c] != '1':
            return
        grid[r][c] = '0'  # mark visited in-place
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            dfs(r+dr, c+dc)

    for r in range(m):
        for c in range(n):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count

Time: O(m*n). Space: O(m*n) recursion stack in worst case (long snake-shaped island). BFS variant: use a queue instead of recursion — avoids stack overflow for very large grids. Union-Find variant: for each 1-cell, union with its right and down neighbors. Count distinct roots at the end. Union-Find is slower here but useful when you need to also answer “are these two cells in the same island” queries dynamically.

Pattern 2: Shortest Path in Matrix (BFS)

Find the shortest path from source to target in a grid with obstacles (LC 1091: shortest path in binary matrix). BFS guarantees shortest path in unweighted graphs. Each BFS level = distance + 1.

from collections import deque

def shortest_path(grid):
    n = len(grid)
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1
    q = deque([(0, 0, 1)])  # (row, col, distance)
    grid[0][0] = 1  # mark visited
    while q:
        r, c, dist = q.popleft()
        if r == n-1 and c == n-1:
            return dist
        for dr in [-1, 0, 1]:
            for dc in [-1, 0, 1]:
                if dr == 0 and dc == 0: continue
                nr, nc = r+dr, c+dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    grid[nr][nc] = 1  # mark visited
                    q.append((nr, nc, dist+1))
    return -1

Key insight: mark cells as visited when enqueuing (not when dequeuing). Marking on dequeue allows duplicate enqueues that waste memory and time. Dijkstra for weighted grids: when cells have different traversal costs, use a min-heap (heapq) instead of a deque. Push (cost, r, c); skip if already visited with lower cost.

Pattern 3: Cycle Detection in Directed Graph

Detect a cycle in a directed graph (LC 207: Course Schedule). DFS with three states: UNVISITED (0), IN_PROGRESS (1), DONE (2). A cycle exists if we reach an IN_PROGRESS node during DFS.

def can_finish(num_courses, prerequisites):
    adj = [[] for _ in range(num_courses)]
    for a, b in prerequisites:
        adj[b].append(a)

    state = [0] * num_courses  # 0=unvisited, 1=in-progress, 2=done

    def dfs(node):
        if state[node] == 1: return False  # cycle
        if state[node] == 2: return True   # already processed
        state[node] = 1
        for nei in adj[node]:
            if not dfs(nei): return False
        state[node] = 2
        return True

    return all(dfs(i) for i in range(num_courses))

Topological sort (Kahn’s algorithm): BFS-based alternative. Compute in-degrees; start from 0-in-degree nodes. If all nodes are processed: no cycle. If some nodes remain unprocessed: cycle exists. Useful when you need the topological order, not just cycle detection.

Pattern 4: Multi-Source BFS and 0-1 BFS

Multi-source BFS: start BFS from multiple sources simultaneously (add all sources to the queue at level 0). Use case: “distance from nearest 0” (LC 542), “rotting oranges” (LC 994). The BFS naturally computes the distance from the nearest source for every cell. 0-1 BFS: edge weights are 0 or 1 (not all equal). Use a deque: push weight-0 neighbors to the front (like free moves), weight-1 neighbors to the back. O(V+E) instead of O((V+E) log V) for Dijkstra. Use case: LC 1368 (minimum cost to make all grid cells reachable with 0/1 edge flipping).

{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”When should you use BFS vs DFS for matrix problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use BFS when you need the shortest path — BFS guarantees the minimum number of steps in an unweighted graph. Use DFS for connected component problems (island counting, flood fill) where you just need to explore all reachable cells, not find the shortest path. Both are O(m*n) for a grid.”}},{“@type”:”Question”,”name”:”Why mark cells as visited when enqueuing rather than when dequeuing in BFS?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Marking on enqueue prevents the same cell from being added to the queue multiple times. If you mark on dequeue, multiple queue entries can exist for the same cell, wasting memory and potentially processing the same cell at wrong distances. Always mark visited immediately when adding to the queue.”}},{“@type”:”Question”,”name”:”How do you detect cycles in a directed graph using DFS?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use three states: UNVISITED (0), IN_PROGRESS (1), DONE (2). During DFS, mark a node IN_PROGRESS when entering. If you reach an IN_PROGRESS node, a cycle exists. Mark nodes DONE after fully exploring their subtree. This correctly distinguishes back edges (cycles) from cross edges (no cycle).”}},{“@type”:”Question”,”name”:”What is multi-source BFS and when is it useful?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Multi-source BFS initializes the queue with multiple source nodes simultaneously (all at distance 0). The BFS then computes the minimum distance from the nearest source for every cell. Classic examples: "distance to nearest 0" (LC 542), "rotting oranges" (LC 994). It is more efficient than running single-source BFS from each source separately.”}},{“@type”:”Question”,”name”:”When should you use Union-Find vs DFS/BFS for connected components?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use DFS or BFS for a one-time connected component scan — simpler code and same O(n) complexity. Use Union-Find when you need to answer repeated "are these two nodes connected?" queries dynamically, or when edges are added incrementally (online algorithm). Union-Find with path compression and union by rank achieves near-O(1) per operation amortized.”}}]}