Number of Islands
Count distinct islands in a grid using depth-first search
Given an m x n 2D binary grid where '1' represents land and '0' represents water, return the number of islands. An island is formed by connecting adjacent lands horizontally or vertically (diagonals do not count).
R — READ
READ
What counts as one island? Can diagonals connect islands?
An island is a group of connected 1s (horizontally or vertically). Diagonals do not count. Each connected group is one island.
Do you understand connectivity? Do you ask about diagonal connections?
Counting diagonally adjacent 1s as part of the same island.
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3 (one 2x2 island, one 1x1 island, one 1x2 island)
O — OBSERVE
OBSERVE
How do I identify connected components?
When I find a '1', I can explore all connected '1's using DFS or BFS. Mark visited cells to avoid revisiting. Each DFS/BFS pass finds one island.
Do you recognize this as a graph connectivity problem? Can you see DFS as a solution?
Trying to count by counting 1s without considering connectivity.
Example: a 2x2 block of 1s
1 1
1 1
This is ONE island, not four.
When I DFS from the top-left 1, I'll visit all four cells.
P — PSEUDOCODE
PSEUDOCODE
What's my approach?
Iterate through grid. When you find a '1', run DFS to mark all connected cells. Increment island count.
Clear DFS logic and cell marking.
Pseudocode that doesn't explain marking visited cells.
1. Initialize island_count = 0
2. For each cell (i, j) in the grid:
a. If grid[i][j] == '1':
i. Increment island_count
ii. DFS from (i, j) to mark all connected '1's as visited
3. Return island_count
DFS helper:
1. Mark current cell as visited (set to '0' or track separately)
2. Recursively visit all four neighbors (up, down, left, right)
3. If neighbor is valid and '1', visit it
I — IMPLEMENT
IMPLEMENT
How do I write DFS cleanly?
Use a helper function for DFS. Mark visited cells by changing them to '0'. Check bounds and cell value before recursing.
Correct recursive DFS and base case handling.
Forgetting to mark visited cells (infinite recursion) or not checking bounds.
def numIslands(grid):
"""
Count the number of islands in a grid.
Args:
grid: List of lists, each cell is '0' (water) or '1' (land)
Returns:
Number of distinct islands
"""
if not grid or not grid[0]:
return 0
def dfs(i, j):
"""Mark all connected land cells as visited."""
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]):
return
if grid[i][j] != '1':
return
# Mark as visited
grid[i][j] = '0'
# Explore all four neighbors
dfs(i + 1, j) # down
dfs(i - 1, j) # up
dfs(i, j + 1) # right
dfs(i, j - 1) # left
island_count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
island_count += 1
dfs(i, j)
return island_count
T — TEST
TEST
Does my code correctly count islands?
Test: single island, multiple islands, no islands, single cell, connected components.
Correctness on various grid structures.
Counting individual '1's instead of connected components.
Test 1: grid = [["1","1"],["1","1"]] → 1 ✓
Test 2: grid = [["1","1"],["0","1"]] → 1 ✓
Test 3: grid = [["1","1"],["1","0"],["0","1"]] → 2 ✓
Test 4: grid = [["0","0"],["0","0"]] → 0 ✓
Test 5: grid = [["1"]] → 1 ✓
A — ANALYZE
ANALYZE
What's the complexity?
We visit each cell once. For each cell, DFS explores connected neighbors. Total: O(m × n).
Correct complexity counting.
Claiming exponential or not accounting for visiting each cell once.
Why: We iterate through all m × n cells. Each cell is visited at most once by DFS (marked as '0' after visit). Total operations: O(m × n). Recursion depth in worst case (a spiral of land) is O(m × n), so space is O(m × n).
Alternative: Use BFS with a queue instead of DFS recursion. Same complexity, but avoids stack overflow on very large grids.