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
• BFS: Shortest path, level-by-level exploration, minimum steps

Common Edge Cases

• Empty grid: grid.length === 0 || grid[0].length === 0
• Single cell grid
• All same value (islands: all 1s or all 0s)
• No valid path exists (return -1)