Grid Search Patterns
Implement and trace classic grid problems: counting islands, flood fill, and multi-source distance maps. Code stems are mostly Python.
901 views
24
Implement numIslands(grid) where grid[r][c] is "1" for land and "0" for water. Two cells are connected if they share an edge (4-directional).
Examples
Example 1:
Input: grid = [['1', '1', '0'], ['1', '0', '0'], ['0', '0', '1']]
Output: 2
Explanation: Scan every cell; on each unseen '1', launch DFS / BFS that sinks the whole component by flipping land to water. Two distinct components: top-left L-shape and bottom-right singleton. O(R * C) time.def num_islands(grid):
# TODO
passTrace the flood fill below on the grid [[1,1,0],[1,0,0],[0,0,1]] starting at (0, 0) with new color 2. What is the grid after the call?
Examples
Example 1:
Input: grid = [[1, 1, 0], [1, 0, 0], [0, 0, 1]]; start (r, c) = (0, 0); new_color = 2
Output: [[2, 2, 0], [2, 0, 0], [0, 0, 1]]
Explanation: Fill starts at (0, 0) with old = 1. Repaints (0, 0), (0, 1), (1, 0) and stops at every 0 boundary. The bottom-right 1 is unreachable. The old == new_color guard prevents an infinite loop.def flood_fill(grid, r, c, new_color):
old = grid[r][c]
if old == new_color:
return grid
R, C = len(grid), len(grid[0])
def go(r, c):
if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] != old:
return
grid[r][c] = new_color
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
go(r + dr, c + dc)
go(r, c)
return gridYou have a grid where each 1 is a source and you want to compute, for every cell, the shortest 4-directional distance to any source. What traversal do you use, and why is a per-source BFS the wrong call?
Fix the bug in this island-perimeter calculator. It should return the number of outward-facing edges of all 1 cells in the grid.
Examples
Example 1:
Input: grid = [[1, 1], [1, 1]]
Output (buggy version): 12
Output (fixed version): 8
Explanation: A shared edge between two land cells hides two outward-facing edges (one from each cell), so each detected neighbor should subtract 2, not 1. Switching both decrements to -= 2 gives the correct perimeter.def island_perimeter(grid):
R, C = len(grid), len(grid[0])
perim = 0
for r in range(R):
for c in range(C):
if grid[r][c] == 1:
perim += 4
if r > 0 and grid[r - 1][c] == 1:
perim -= 1
if c > 0 and grid[r][c - 1] == 1:
perim -= 1
return perimWhat is the worst-case time complexity of BFS or DFS on an R x C grid with 4-directional moves, and why is it O(R * C) rather than O((R * C)^2)?