Number of Islands
Problem
Given a 2D grid map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
- m == grid.length
- n == grid[i].length
- 1 ≤ m, n ≤ 300
- grid[i][j] is '0' or '1'
Example
grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]3The grid contains three islands. The first island is formed by the top-left four '1's connected horizontally and vertically. The second island is the single '1' at position (2,2). The third island consists of the two connected '1's at the bottom-right corner. The DFS explores each island fully, marking visited land cells to avoid double counting.
Approach
Straightforward Solution
A brute-force approach would scan the grid and for each '1' found, perform a DFS or BFS to mark all connected '1's as visited, incrementing the island count. Without marking visited cells, the algorithm would count the same island multiple times.
Core Observation
Islands are connected components of '1's in a grid, where connectivity is defined horizontally and vertically. The problem reduces to counting connected components in a grid graph.
Path to Optimal
The key insight is to use DFS to explore all connected land cells starting from an unvisited '1'. By marking visited cells, the algorithm avoids revisiting and recounting the same island. This approach ensures each cell is processed once, leading to an O(m*n) time complexity. The visited set prevents infinite loops and redundant work.
Optimal Approach
Iterate over every cell in the grid. When an unvisited land cell ('1') is found, initiate a DFS to mark all connected land cells as visited. Increment the island count by one for each such DFS initiation. The DFS recursively explores neighbors in four directions, stopping at water, visited cells, or out-of-bounds indices. This guarantees each island is counted exactly once.
Time
O(m * n)
Each cell is visited at most once during the DFS traversal or the main iteration. The DFS explores neighbors recursively but never revisits visited cells, resulting in linear time proportional to the grid size.
Space
O(m * n)
The visited set can store up to all cells in the grid in the worst case (all land). The recursion stack depth can be up to O(m * n) in the worst case of a single large island, which is acceptable for this problem.
Pattern Spotlight
DFS (Connected Components in Grid)
When counting islands or connected regions in a grid, use DFS to fully explore and mark each connected component starting from an unvisited land cell, ensuring no double counting and linear time complexity.
Solution
| 1 | class Solution:
|
| 2 | def numIslands(self, grid: list[list[str]]) -> int:
|
| 3 | if not grid:
|
| 4 | return 0
|
| 5 |
|
| 6 | ROWS, COLS = len(grid), len(grid[0])
|
| 7 | visited = set()
|
| 8 | islands = 0
|
| 9 |
|
| 10 | def dfs(r, c):
|
| 11 | if (r not in range(ROWS) or
|
| 12 | c not in range(COLS) or
|
| 13 | grid[r][c] == '0' or
|
| 14 | (r, c) in visited):
|
| 15 | return
|
| 16 |
|
| 17 | visited.add((r, c))
|
| 18 | dfs(r + 1, c)
|
| 19 | dfs(r - 1, c)
|
| 20 | dfs(r, c + 1)
|
| 21 | dfs(r, c - 1)
|
| 22 |
|
| 23 | for r in range(ROWS):
|
| 24 | for c in range(COLS):
|
| 25 | if grid[r][c] == '1' and (r, c) not in visited:
|
| 26 | dfs(r, c)
|
| 27 | islands += 1
|
| 28 |
|
| 29 | return islands |
Step-by-Step Solution
Handle Empty Grid Edge Case
| 3 | if not grid:
|
| 4 | return 0
|
Objective
To immediately return 0 if the input grid is empty, as no islands can exist.
Key Insight
An empty grid means there are no cells to explore, so the number of islands is trivially zero. Handling this edge case upfront avoids errors in subsequent code that assumes a non-empty grid.
Interview Quick-Check
State & Boundaries
Check if the grid is empty before accessing its dimensions to prevent index errors.
Initialize Grid Dimensions, Visited Set, and Island Counter
| 6 | ROWS, COLS = len(grid), len(grid[0])
|
| 7 | visited = set()
|
| 8 | islands = 0
|
Objective
To prepare the necessary variables for grid traversal and tracking visited land cells.
Key Insight
Storing the number of rows and columns upfront simplifies boundary checks. The visited set tracks which land cells have been explored to avoid double counting. The islands counter accumulates the total number of distinct islands found.
Interview Quick-Check
Core Logic
The visited set is essential to prevent revisiting cells and infinite recursion during DFS.
Complexity
Initializing these variables is O(1) and sets the stage for efficient traversal.
Recursively Explore Connected Land Cells via DFS
| 10 | def dfs(r, c):
|
| 11 | if (r not in range(ROWS) or
|
| 12 | c not in range(COLS) or
|
| 13 | grid[r][c] == '0' or
|
| 14 | (r, c) in visited):
|
| 15 | return
|
| 17 | visited.add((r, c))
|
| 18 | dfs(r + 1, c)
|
| 19 | dfs(r - 1, c)
|
| 20 | dfs(r, c + 1)
|
| 21 | dfs(r, c - 1)
|
Objective
To perform a depth-first search that marks all land cells connected to the starting cell as visited.
Key Insight
DFS explores neighbors in four directions, stopping when encountering water, visited cells, or out-of-bounds indices. This ensures the entire island is fully traversed and marked, preventing partial counting or revisits. The recursive calls propagate until all connected land is exhausted.
Interview Quick-Check
Core Logic
The DFS base case checks for out-of-bounds, water, or visited cells to terminate recursion correctly.
State & Boundaries
Marking the current cell as visited before recursive calls prevents cycles and redundant exploration.
Common Pitfalls & Bugs
Forgetting to mark cells as visited before recursive calls can cause infinite recursion or overcounting.
Iterate Over Grid to Identify and Count Islands
| 23 | for r in range(ROWS):
|
| 24 | for c in range(COLS):
|
| 25 | if grid[r][c] == '1' and (r, c) not in visited:
|
| 26 | dfs(r, c)
|
| 27 | islands += 1
|
Objective
To scan every cell in the grid and initiate DFS for each unvisited land cell, incrementing the island count accordingly.
Key Insight
By iterating through all cells, the algorithm ensures no island is missed. Starting DFS only on unvisited land cells guarantees each island is counted once. Incrementing the island count after each DFS call reflects the discovery of a new island.
Interview Quick-Check
Core Logic
The nested loops cover every cell systematically, ensuring complete coverage of the grid.
State & Boundaries
The condition to start DFS only on unvisited land cells prevents redundant counting.
Complexity
Each cell is processed once, either during iteration or DFS, ensuring O(m*n) time.
Return Total Number of Islands Found
| 29 | return islands |
Objective
To output the final count of distinct islands after full grid traversal.
Key Insight
After all DFS explorations, the islands variable holds the total number of connected land components. Returning this value completes the problem's requirement.
Interview Quick-Check
Core Logic
Returning the islands count reflects the total number of connected components found.
Line Analysis
This solution has 7 Critical lines interviewers watch for.
(r, c) in visited):Check if the current cell has already been visited.
Avoids revisiting cells, which prevents infinite recursion and double counting of land cells.
visited.add((r, c))Mark the current cell as visited.
Marking before recursive calls prevents cycles and ensures each land cell is processed exactly once.
dfs(r, c)Invoke DFS to explore the entire island connected to the current cell.
This call fully explores and marks all connected land cells, ensuring the island is counted once.
visited = set()Initialize a set to track visited land cells.
The visited set prevents revisiting cells, which is essential to avoid infinite recursion and double counting islands.
grid[r][c] == '0' orCheck if the current cell is water ('0').
Water cells are not part of islands, so recursion stops here to avoid exploring irrelevant paths.
if grid[r][c] == '1' and (r, c) not in visited:Check if the current cell is land and unvisited.
Starting DFS only on unvisited land cells prevents redundant exploration and double counting.
islands += 1Increment the island count after fully exploring a new island.
Each DFS initiation corresponds to discovering a new island, so incrementing here correctly counts islands.
if (r not in range(ROWS) orCheck if row index is out of bounds.
This boundary check prevents invalid grid access and terminates recursion when outside the grid vertically.
c not in range(COLS) orCheck if column index is out of bounds.
This boundary check prevents invalid grid access and terminates recursion when outside the grid horizontally.
returnReturn from DFS if any base case is met.
This line terminates the recursion when the exploration reaches invalid or already processed cells, ensuring correctness and efficiency.
return islandsReturn the total number of islands found.
After complete traversal and exploration, this returns the final count of distinct islands.
if not grid:Check if the input grid is empty.
This early check prevents errors from accessing grid dimensions when the grid is empty and correctly returns zero islands in this trivial case.
return 0Return 0 immediately if the grid is empty.
No cells exist to form islands, so the correct answer is zero, avoiding further unnecessary computation.
dfs(r + 1, c)Recursively explore the cell below the current cell.
DFS explores all connected land vertically downward to fully traverse the island.
dfs(r - 1, c)Recursively explore the cell above the current cell.
DFS explores all connected land vertically upward to fully traverse the island.
dfs(r, c + 1)Recursively explore the cell to the right of the current cell.
DFS explores all connected land horizontally rightward to fully traverse the island.
dfs(r, c - 1)Recursively explore the cell to the left of the current cell.
DFS explores all connected land horizontally leftward to fully traverse the island.
def dfs(r, c):Define the DFS helper function to explore connected land.
Encapsulating DFS logic in a helper function organizes the recursive exploration of connected components.
for r in range(ROWS):Iterate over each row in the grid.
Systematically scanning every cell ensures no island is missed.
for c in range(COLS):Iterate over each column in the current row.
Nested iteration covers every cell in the 2D grid.
ROWS, COLS = len(grid), len(grid[0])Store the number of rows and columns in the grid.
Caching these values simplifies boundary checks and avoids repeated calls to len() during traversal.
islands = 0Initialize the island counter to zero.
This variable accumulates the total number of distinct islands found during traversal.
Test Your Understanding
Why is it necessary to mark cells as visited during DFS when counting islands?
Marking cells as visited prevents revisiting the same land cell multiple times, which would cause overcounting islands and infinite recursion. It ensures each island is counted exactly once by fully exploring and marking all connected land cells.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Number of Islands from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Number of Islands drill