Input: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]] → Output: 3
For each unvisited '1' cell, flood-fill the entire island. Each new flood fill increments the island count.
TimeO(R×C)visit each cell once
SpaceO(R×C)visited set + queue
Visited: 0/7Queue: 0Islands: 0
Processing
In Queue
Island 1
Island 2
Island 3
Unvisited land
Water
Queue
empty
Visited
{ }
Count
0
Ready
Press Play to watch BFS flood fill discover islands, or Step to advance one operation at a time.
Each unvisited '1' cell triggers a new BFS, marking one complete island.
TimeO(R×C)sink each land cell once
SpaceO(R×C)recursive call stack
Recursive DFS
Walk the grid. When a '1' is found, increment the count and recursively
sink its four connected neighbors to '0'. The boundary/water check is
the recursion base case.
✎ Whiteboard
3
⌨ Type It — Iterative BFS
Practice until you don't need to look. Use the guide comments below as scaffolding. Type the full implementation in the editor. The green highlights are the nuances to burn into memory.
═══ NUMBER OF ISLANDS — BFS FLOOD FILL ═══
PATTERN ▸ BFS per unvisited '1' O(R×C) · O(R×C)
① IMPORT & DEFINE
from collections import deque
def numIslands(self, grid)
② BFS HELPER
def bfs(r, c):
queue = deque([(r, c)])
visited.add((r, c))
while queue:
row, col = queue.popleft()
for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
nr, nc = row+dr, col+dc
if 0<=nr<R and 0<=nc<C and grid[nr][nc]=='1' and (nr,nc) not in visited:
visited.add((nr, nc)); queue.append((nr, nc))
③ MAIN LOOP
R, C = len(grid), len(grid[0])
count = 0; visited = set()
for r in range(R): for c in range(C):
if grid[r][c]=='1' and (r,c) not in visited:
count += 1; bfs(r, c)
return count
▼ your implementation ▼
Verify your solution:
⌨ Type It — Recursive DFS
Practice until you don't need to look. Use the guide comments below as scaffolding. The green highlights are the nuances to burn into memory.