Question Bank
Grid Search Patterns
Difficulty: Medium
Implement and trace classic grid problems: counting islands, flood fill, and multi-source distance maps. Code stems are mostly Python.
Grid Search Patterns
Implement and trace classic grid problems: counting islands, flood fill, and multi-source distance maps. Code stems are mostly Python.
900 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.Trace 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.You 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.What 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)?