行列とグリッド問題

Number of Islands: scan the grid; when you find a 1, run DFS/BFS to mark the entire island as visited, then increment your count.

def num_islands(grid):
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == '1':
                dfs(grid, r, c)  # mark island
                count += 1
    return count

Rotting Oranges - Multi-Source BFS

All initially rotten oranges are sources. Push them all into the queue at time 0, then BFS. Each level is one minute. When the queue empties, check if any fresh oranges remain.

Minute 0:  [2, 1, 1]    2 = rotten, 1 = fresh
           [1, 1, 0]
           [0, 1, 1]

Minute 4:  [2, 2, 2]    All reachable oranges rotten
           [2, 2, 0]
           [0, 2, 2]

The key insight: multi-source BFS starts from multiple nodes simultaneously, not one.

Spiral Matrix Traversal

Walk the matrix in spiral order: right → down → left → up, shrinking boundaries after each pass.

def spiral(matrix):
    res = []
    top, bot = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bot and left <= right:
        for c in range(left, right + 1):
            res.append(matrix[top][c])
        top += 1
        for r in range(top, bot + 1):
            res.append(matrix[r][right])
        right -= 1
        if top <= bot:
            for c in range(right, left - 1, -1):
                res.append(matrix[bot][c])
            bot -= 1
        if left <= right:
            for r in range(bot, top - 1, -1):
                res.append(matrix[r][left])
            left += 1
    return res

Matrix Rotation (90°)

Rotate an N×N matrix clockwise in-place: transpose (swap [r][c] with [c][r]), then reverse each row.

Original → Transpose → Reverse rows
1 2 3     1 4 7       7 4 1
4 5 6  →  2 5 8   →   8 5 2
7 8 9     3 6 9       9 6 3

Search in a Sorted 2D Matrix

Two common variants:

• Rows and columns sorted independently - start from the top-right corner. If the target is smaller, move left; if larger, move down. O(m + n).
• Fully sorted (each row starts where the previous ends) - treat as a flat sorted array and binary search. O(log(m × n)).

Dynamic Programming on Grids

Unique Paths: count paths from top-left to bottom-right moving only right or down. dp[r][c] = dp[r-1][c] + dp[r][c-1].

Minimum Path Sum: same idea but pick the minimum incoming path.

These are often the gentlest introduction to 2D dynamic programming.

Grid Patterns Cheat Sheet

| Pattern | Technique | Key Problem | |---------|-----------|-------------| | Shortest path (unweighted) | BFS | Maze shortest path | | Connected components | DFS / BFS | Number of Islands | | Multi-source spread | Multi-source BFS | Rotting Oranges | | Traversal order | Boundary pointers | Spiral Matrix | | In-place transform | Transpose + reverse | Rotate Image | | Counting paths | DP | Unique Paths | | Search in sorted grid | Staircase / binary search | Search 2D Matrix |

📚 Further Reading

• NeetCode - 2D Dynamic Programming - grid DP problems with visual explanations
• Tech Interview Handbook - Matrix - common patterns and techniques
• LeetCode Matrix tag - hundreds of practice problems