Matrix Traversal Patterns

Core Setup: 4-Directional Movement

const DIRECTIONS = [[0, 1], [1, 0], [0, -1], [-1, 0]]

function isValid(row: number, col: number, grid: any[][]): boolean {
  return row >= 0 && row < grid.length && 
         col >= 0 && col < grid[0].length
}

Pattern 1: DFS (Number of Islands)

function numIslands(grid: string[][]): number {
  let count = 0
  const visited = new Set<string>()
  
  function dfs(r: number, c: number) {
    const key = `${r},${c}`
    if (!isValid(r, c, grid) || visited.has(key) || grid[r][c] === '0') return
    
    visited.add(key)
    for (const [dr, dc] of DIRECTIONS) dfs(r + dr, c + dc)
  }
  
  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === '1' && !visited.has(`${r},${c}`)) {
        dfs(r, c)
        count++
      }
    }
  }
  
  return count
}
// DFS marks entire island, then increment counter

Pattern 2: BFS (Shortest Path)

function shortestPath(grid: number[][]): number {
  const queue: [number, number, number][] = [[0, 0, 0]] // [row, col, dist]
  const visited = new Set<string>(['0,0'])
  
  while (queue.length) {
    const [r, c, dist] = queue.shift()!
    
    if (r === grid.length - 1 && c === grid[0].length - 1) return dist
    
    for (const [dr, dc] of DIRECTIONS) {
      const nr = r + dr, nc = c + dc
      const key = `${nr},${nc}`
      
      if (isValid(nr, nc, grid) && !visited.has(key) && grid[nr][nc] === 0) {
        visited.add(key)
        queue.push([nr, nc, dist + 1])
      }
    }
  }
  
  return -1
}
// BFS guarantees shortest path in unweighted grid

Pattern 3: Flood Fill

function floodFill(image: number[][], sr: number, sc: number, color: number): number[][] {
  const original = image[sr][sc]
  if (original === color) return image
  
  function fill(r: number, c: number) {
    if (!isValid(r, c, image) || image[r][c] !== original) return
    image[r][c] = color
    for (const [dr, dc] of DIRECTIONS) fill(r + dr, c + dc)
  }
  
  fill(sr, sc)
  return image
}

When to Use DFS vs BFS

• DFS: Counting regions, exploring all paths, flood fill, cycle detection
• BFS: Shortest path, level-by-level exploration, minimum steps, multi-source spreading

Pattern 4: Multi-Source BFS (Rotting Oranges)

Start BFS from multiple sources simultaneously. Classic example: spreading fire/rot from all infected cells at once.

function orangesRotting(grid: number[][]): number {
  const queue: [number, number][] = []
  let fresh = 0
  
  // Seed BFS with all rotten oranges
  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === 2) queue.push([r, c])
      if (grid[r][c] === 1) fresh++
    }
  }
  
  let minutes = 0
  while (queue.length && fresh > 0) {
    const size = queue.length
    for (let i = 0; i < size; i++) {
      const [r, c] = queue.shift()!
      for (const [dr, dc] of DIRECTIONS) {
        const nr = r + dr, nc = c + dc
        if (isValid(nr, nc, grid) && grid[nr][nc] === 1) {
          grid[nr][nc] = 2
          fresh--
          queue.push([nr, nc])
        }
      }
    }
    minutes++
  }
  return fresh === 0 ? minutes : -1
}

Common Edge Cases

• Empty grid: grid.length === 0 || grid[0].length === 0
• Single cell grid: check before pushing to queue/recursing
• All same value (islands: all 1s or all 0s)
• No valid path exists (return -1)
• Modifying the grid in-place vs using a separate visited set: trade speed for memory

Complexity Reference

• DFS / BFS on m×n grid: O(m×n) time, O(m×n) space for visited set
• In-place modification (flip visited cell): O(1) extra space, but destructive
• Multi-source BFS: same asymptotic complexity, but reduces constant factor vs running BFS for each source

Problems to Practice

• Number of Islands (LC 200) - DFS/BFS region counting
• Max Area of Island (LC 695) - DFS with area tracking
• Flood Fill (LC 733) - DFS in-place modification
• Shortest Path in Binary Matrix (LC 1091) - BFS 8-directional
• Rotting Oranges (LC 994) - Multi-source BFS
• Pacific Atlantic Water Flow (LC 417) - Reverse multi-source DFS