1. Number of Islands (LeetCode)
Model answer
The task
Given a grid of land and water, count the groups of connected land cells. Cells connect horizontally or vertically, not diagonally.
Key idea
Each group is one island. Scan the grid, and whenever an unvisited land cell is found, count a new island and explore its entire connected region. Mark cells as visited when adding them to the search queue so no cell is processed more than once.
Approach
- Return
0if the grid is empty. - Scan every cell in the grid.
- When a land cell is found, increment the island count and start a breadth-first search from it.
- During the search, mark each discovered land cell as water and add its in-bounds land neighbors to the queue.
- Return the island count after the scan is complete.
from collections import deque
from typing import List
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
islands = 0
for row in range(rows):
for col in range(cols):
if grid[row][col] != "1":
continue
islands += 1
grid[row][col] = "0"
queue = deque([(row, col)])
while queue:
current_row, current_col = queue.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
next_row = current_row + dr
next_col = current_col + dc
if (
0 <= next_row < rows
and 0 <= next_col < cols
and grid[next_row][next_col] == "1"
):
# Mark when enqueuing to avoid duplicate work.
grid[next_row][next_col] = "0"
queue.append((next_row, next_col))
return islands
Complexity: Time: O(rows * cols), since each cell is examined at most a constant number of times.
Complexity: Space: O(rows * cols) in the worst case for the BFS queue.
Common follow-ups
- Preserve the input grid? Track visited cells in a separate set instead of changing land cells to water.
- Use depth-first search instead? Recursively or iteratively explore the four neighbors; iterative DFS avoids recursion-depth concerns.
- Count diagonally connected land as part of the same island? Include the four diagonal directions in the neighbor list.