200. Number of Islands
Model: qwen3.5:9b
Topics: Depth-first Search,Breadth-first Search,Union Find
FAANG asked: 1
Acceptance rate: 49.5%
Problem Breakdown
We need to count distinct connected components of land ('1') in a 2D binary grid. Connectivity is defined by horizontal and vertical adjacency (4-directional). Water ('0') acts as a separator between islands, but does not contribute to the count itself.
Inputs: A list of lists representing rows and columns containing '0' or '1'.
Output: An integer representing the total number of distinct islands found.
Implicit Constraints & Edge Cases:
- Grid Dimensions: The problem constraints state
m, n >= 1, but in a real-world scenario (or strict interview defense), we should handle an empty grid gracefully by returning 0 immediately if possible or relying on loop bounds to naturally skip it. - Connectivity: Diagonal connections do not count as part of the same island.
- In-place Modification: To optimize space, marking visited land cells (e.g., changing
'1'to'0') is a standard technique in this problem type to avoid maintaining an extravisitedset.
Intuition
If we simply iterate through every cell and count the number of '1's, we will overcount because adjacent lands belong to the same island.
The core insight for connected components problems like this is Flood Fill. When we encounter a land cell ('1') that hasn’t been visited yet:
- We know it belongs to a new island, so we increment our counter.
- To ensure we don’t count any part of this island again later in the traversal, we must mark all reachable connected
'1's as “visited.”
We can achieve this marking by changing the land cell value from '1' to '0' (effectively turning it into water) during our search. This modifies the input grid but saves us O(M*N) space for a separate visited set, keeping auxiliary space proportional only to the traversal stack/queue depth.
DFS or BFS are both suitable here. DFS is often more concise in Python using recursion or an explicit stack. I will use iterative DFS with a stack list to avoid potential RecursionError on deep grids (though 300x300 might hit default limits, iterative is safer for production). Union-Find could also work but adds overhead of parent array initialization and path compression logic that isn’t strictly necessary compared to simple traversal.
Approach
- Initialize a counter
islands = 0. - Iterate through every cell
(i, j)in the grid using nested loops. - If we find a
'1':- Increment
islands(we found a new island). - Start a traversal from this cell to visit all connected land cells belonging to this specific island.
- Increment
- During traversal:
- Check bounds and if the current neighbor is still
'1'. - If valid, mark it as visited by setting
grid[r][c] = '0'(modifying in-place).
- Check bounds and if the current neighbor is still
- Continue until all reachable land from this starting point has been marked water.
- Return the final count after checking every cell.
Complexity Analysis
- Time: O(m * n) where m is rows and n is columns. We visit each cell at most twice: once in the outer loop, and potentially once during a traversal (DFS/BFS). Each operation inside the loops is constant time.
- Space: O(k), where k is the maximum depth of recursion or size of the queue/stack used for traversal. In the worst case (all cells are connected land), this approaches O(m * n) stack space, though typically much smaller on average grids. If we consider modifying the grid in-place as part of the input state rather than auxiliary storage, it is effectively constant relative to a separate visited array allocation.
Solution
from typing import List
def numIslands(grid: List[List[str]]) -> int:
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
islands_count = 0
# Directions for moving up, down, left, right
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def dfs(r: int, c: int):
stack = [(r, c)]
while stack:
curr_r, curr_c = stack.pop()
# Check all four neighbors
for dr, dc in directions:
nr, nc = curr_r + dr, curr_c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == '1':
# Mark as visited immediately to prevent re-processing
grid[nr][nc] = '0'
stack.append((nr, nc))
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
islands_count += 1
dfs(i, j) # Flood fill this entire island
return islands_count
Edge Cases Handled
- Empty Grid: The initial check
if not grid or not grid[0]:returns 0 immediately if the input is empty. - All Water: If no
'1'exists, the outer loops finish without incrementingislands_count, returning 0 correctly. - Single Island (Full Grid): The DFS will traverse every cell once; time complexity remains linear O(m*n).
- Disconnected Islands: Each disconnected component triggers a new counter increment and separate traversal pass.