Grid / Matrix Problems

Definition

Grid problems treat each cell as a graph node connected to up/down/left/right neighbors.

Number of islands, rotting oranges and flood fill are common interview questions.

Diagram

Flowchart

Example: Number of islands

g = [[1,1,0],[0,1,0],[0,0,1]]
def dfs(r, c):
    if 0 <= r < 3 and 0 <= c < 3 and g[r][c]:
        g[r][c] = 0
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): dfs(r+dr, c+dc)
cnt = 0
for r in range(3):
    for c in range(3):
        if g[r][c]: dfs(r, c); cnt += 1
print(cnt)

Output: 2

Complexity

O(rows × cols)

Key points

• Use a directions list
• Multi-source BFS for shortest spread time

Interview questions

More DSA topics