行列とグリッド問題

2D Arrays as Grids

A matrix is just a 2D array, but in interviews it often represents a grid - a map, a board, or a maze. Each cell grid[r][c] is a node, and its neighbours are adjacent cells.

grid = [
  [1, 1, 0],
  [1, 0, 0],
  [0, 0, 1]
]

Row r, column c, dimensions m × n. Simple - but the patterns built on top are powerful.

Directional Arrays

Instead of writing four separate if-statements, use a direction array:

# 4-directional (up, down, left, right)
dirs = [(-1,0), (1,0), (0,-1), (0,1)]

# 8-directional (includes diagonals)
dirs = [(-1,0),(1,0),(0,-1),(0,1),
        (-1,-1),(-1,1),(1,-1),(1,1)]

for dr, dc in dirs:
    nr, nc = r + dr, c + dc
    if 0 <= nr < m and 0 <= nc < n:
        # process neighbour

This is the single most reusable snippet in grid problems.

BFS on a Grid - Shortest Path in a Maze

BFS finds the shortest path in an unweighted grid. Start from the source, explore all neighbours at distance 1, then distance 2, and so on.

from collections import deque

def shortest_path(grid, start, end):
    m, n = len(grid), len(grid[0])
    q = deque([(start[0], start[1], 0)])
    visited = {(start[0], start[1])}
    dirs = [(-1,0),(1,0),(0,-1),(0,1)]
    while q:
        r, c, dist = q.popleft()
        if (r, c) == end:
            return dist
        for dr, dc in dirs:
            nr, nc = r+dr, c+dc
            if 0<=nr<m and 0<=nc<n and (nr,nc) not in visited and grid[nr][nc]==0:
                visited.add((nr, nc))
                q.append((nr, nc, dist+1))
    return -1

DFS on a Grid - Flood Fill and Number of Islands

Flood fill (like the paint bucket tool): from a starting cell, change all connected cells of the same colour. DFS or BFS both work.

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