Number of Islands

BFS/DFS Flood Fill on 2D Grid

LeetCode 200 • Medium • Graphs

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, run BFS to mark the entire island. Count how many BFS calls = islands.

Time O(R×C) visit each cell once

Space O(R×C) visited set + queue

Visited: 0/7 Queue: 0 Islands: 0

Processing

In Queue

Island 1

Island 2

Island 3

Unvisited land

Water

Queue

empty

Visited

{ }

Count

Speed:

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.

✎ Whiteboard

Size: 3

⌨ Type It — Build Muscle Memory

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 (LeetCode 200) ───

# Pattern: BFS flood fill per unvisited '1'

# Time: O(R×C) Space: O(R×C)

# 1. Import: from collections import deque

# 2. Define: def numIslands(self, grid)

# 3. BFS helper (closure over visited, grid):

# def bfs(r, c):

# queue = deque([(r, c)])

# visited.add((r, c)) ← mark BEFORE loop

# 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

# visited.add((nr, nc))

# queue.append((nr, nc))

# 4. Main loop (iterate grid):

# 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

# Key: each BFS discovers ONE complete island (4-direction neighbors)

# Vars: grid, queue (deque), visited (set), count

▼ your implementation ▼

Verify your solution: