Example 1
ready- Input
grid = [ [ "1", "1", "0", "0", "0" ], [ "1", "1", "0", "0", "0" ], [ "0", "0", "1", "0", "0" ], [ "0", "0", "0", "1", "1" ] ]- Expected
3- Why
- the top-left block, center cell, and bottom-right pair are three islands
Number of Islands
35 min · numIslands()mediumOpen in LeetCode #200 ↗
A satellite sends you a blocky map: land is marked "1", water is marked "0".
The useful question isn't how much land you see. It's how many separate land masses
the map contains.
An island is one or more land cells connected through shared top, bottom, left, or
right edges. Given grid, return its number of islands.
A few ground rules:
- Diagonal contact doesn't join two islands.
- Every cell is a single-character string:
"1"for land or"0"for water. - The grid is rectangular, so every row has the same width.
Constraints
1 <= grid.length <= 3001 <= grid[r].length <= 300- Every row has the same length.
grid[r][c]is either"0"or"1".
Hints
Find one shoreline
Scan the board. The first unvisited land cell you meet belongs to an island you haven't counted yet.
Consume the whole island
After counting that first cell, walk through all connected land. Mark each visited cell as water so the outer scan can't count the same island again.
Keep movement orthogonal
Your traversal has exactly four directions. Adding diagonals silently changes the meaning of an island and breaks checkerboard cases.
Follow-up
If you weren't allowed to modify grid, what extra structure would you use to remember
the land cells you've already visited?
Visible cases
Examples
Example 2
ready- Input
grid = [ [ "1", "1", "1", "1", "0" ], [ "1", "1", "0", "1", "0" ], [ "1", "1", "0", "0", "0" ], [ "0", "0", "0", "0", "0" ] ]- Expected
1- Why
- every land cell connects back to the same large island
Example 3
ready- Input
grid = [ [ "1", "0", "1" ], [ "0", "1", "0" ], [ "1", "0", "1" ] ]- Expected
5- Why
- diagonal land cells don't connect, so each one stands alone
Interview signal
Asked at
AmazonGoogleMetaBloomberg
Union–find sweep — merge neighboring land
Union–find is a structure that tracks which items belong to the same connected group. Start with every land cell as its own group. While scanning, merge it with the land cell to its right and the one below it. Each successful merge reduces the island count by one.
def num_islands(grid: list[list[str]]) -> int:
rows, cols = len(grid), len(grid[0])
total = rows * cols
parent = list(range(total))
size = [1] * total
def find(node: int) -> int:
while parent[node] != node:
node = parent[node]
return node
def union(a: int, b: int) -> bool:
root_a, root_b = find(a), find(b)
if root_a == root_b:
return False
if size[root_a] < size[root_b]:
root_a, root_b = root_b, root_a
parent[root_b] = root_a
size[root_a] += size[root_b]
return True
islands = sum(cell == "1" for row in grid for cell in row)
for row in range(rows):
for col in range(cols):
if grid[row][col] == "0":
continue
here = row * cols + col
if row + 1 < rows and grid[row + 1][col] == "1":
islands -= union(here, (row + 1) * cols + col)
if col + 1 < cols and grid[row][col + 1] == "1":
islands -= union(here, row * cols + col + 1)
return islandsMerging smaller trees under larger ones keeps their height logarithmic. Time O(mn log(mn)). Space O(mn) for the parent and size arrays.
Grid DFS — sink each island once
The direct grid DFS treats land cells as graph nodes and walks depth-first through
their four neighbors. When the outer scan finds "1", count one new island and launch a
DFS that changes its entire connected region to "0". Later scan positions then see water,
not an island you've already counted.
def num_islands(grid: list[list[str]]) -> int:
rows, cols = len(grid), len(grid[0])
islands = 0
for start_row in range(rows):
for start_col in range(cols):
if grid[start_row][start_col] != "1":
continue
islands += 1
grid[start_row][start_col] = "0"
stack = [(start_row, start_col)]
while stack:
row, col = stack.pop()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = row + dr, col + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
grid[nr][nc] = "0"
stack.append((nr, nc))
return islandsMark a cell when you add it to the stack, not when you remove it. That prevents two neighbors from adding the same cell twice. Time O(mn) because every cell is scanned and each land cell is sunk once. Space O(mn) in the worst case for the DFS stack.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
3
Run: visible + custom · Submit: full suite