Difficulty: Medium | Asked at: Amazon, Google, Meta
Given a 2D grid of
'1' (land) and '0' (water), count the number of islands (connected groups of land, horizontally/vertically).
Input:
11000
11000
00100
00011
Output: 3
💡 Hint: This is graph traversal on an implicit grid graph - each land cell is a node, adjacent land cells are connected edges. DFS or BFS, "sinking" each island as you find it so you don't count it twice.
Solution:
python
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def sink(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0' # mark as visited by sinking it
sink(r+1, c)
sink(r-1, c)
sink(r, c+1)
sink(r, c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
sink(r, c)
return count
Complexity: O(rows × cols) time - every cell is visited a constant number of times. Space is O(rows × cols) worst case for the recursion stack, if the entire grid is one giant island.
Common mistake: Modifying the grid in place without realizing that mutates the input the caller passed in - perfectly fine for most interview settings, but worth mentioning out loud: "I'm mutating the grid directly to track visited cells - if we need to preserve the original input, I'd use a separate visited set instead."
This exact pattern - grid + DFS/BFS + "sinking"/marking visited - solves a huge family of "connected regions" problems. Worth having memorized cold.
Would you use DFS or BFS here, and does it actually matter for this particular problem? 👇