Number of Islands
Count the number of connected groups of 1s in a grid.
MediumSolve on LeetCode
Examples
Input:grid = [['1','1','0'], ['1','1','0'], ['0','0','1']]
Output:2
Explain:
Island 1 (Top Left), Island 2 (Bottom Right).
Problem Understanding
An m x n grid marks land with '1' and water with '0'. Count the islands: groups of land cells joined through up, down, left or right neighbours, with water or the grid's edge all around them.
Algorithm Strategy
We need to find Connected Components.
- Iterate: Loop through every cell
(r, c)of the grid. - Trigger: If we find a land cell
'1', we found a NEW island!- Increment
count. - Sink the Island: Launch DFS from this cell to visit all connected lands and mark them as visited (e.g., change '1' to '0').
- Increment
- Continue: If we see a '0' (or visited cell), skip it.
Visualization
Scan the grid row by row. When the scan finds land, the island counter goes up and DFS sinks every cell of that island to '0', calling down, up, right, then left. Each island keeps its own colour after it is sunk, so when the scan later passes over those cells you can see they were already counted.
Dry Run
Grid:
1 1 0
1 0 0
0 0 1
| Step | Where | Action | Islands |
|---|---|---|---|
| 1 | scan (0,0) |
'1' — new island. islands = 1. Call dfs(0,0). |
1 |
| 2 | dfs(0,0) |
Sink (0,0). Call down. |
1 |
| 3 | dfs(1,0) |
Sink (1,0). Down (2,0) is water, up (0,0) is already sunk, right (1,1) is water, left (1,-1) is outside — all return. |
1 |
| 4 | back in dfs(0,0) |
Up (-1,0) is outside — returns. Call right. |
1 |
| 5 | dfs(0,1) |
Sink (0,1). Down (1,1) is water, up (-1,1) is outside, right (0,2) is water, left (0,0) is already sunk — all return. |
1 |
| 6 | back in dfs(0,0) |
Left (0,-1) is outside — returns. The first island is fully sunk. |
1 |
| 7 | scan (0,1) to (2,1) |
(0,1) and (1,0) are now '0'; (0,2), (1,1), (1,2), (2,0) and (2,1) are water — all skipped. |
1 |
| 8 | scan (2,2) |
'1' — new island. islands = 2. Call dfs(2,2). |
2 |
| 9 | dfs(2,2) |
Sink (2,2). Down and right are outside; up (1,2) and left (2,1) are water — all return. |
2 |
| End | — | Every cell scanned. Return 2. | 2 |
Edge Cases & Common Mistakes
- Out of Bounds: Always check
r < 0,c < 0,r >= rows,c >= colsfirst in DFS. - Cyclic Dependency: Without marking
visited(or changing '1' to '0'), DFS will run infinitely in a loop of lands. - All Water: No cell is
1, so no DFS ever starts and the answer is 0. (LeetCode guarantees at least one row and one column.) - Diagonal Connection: The problem usually specifies horizontal/vertical connections only (4-way). Don't include diagonals unless specified.
Solution (Sinking Method)
Modifying the grid in-place to save space.
Number of Islands Code
1var numIslands = function(grid) {2 const rows = grid.length, cols = grid[0].length;34 function dfs(r, c) {5 if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') {6 return;7 }8 grid[r][c] = '0';9 dfs(r + 1, c);10 dfs(r - 1, c);11 dfs(r, c + 1);12 dfs(r, c - 1);13 }1415 let islands = 0;16 for (let r = 0; r < rows; r++) {17 for (let c = 0; c < cols; c++) {18 if (grid[r][c] === '1') {19 islands++;20 dfs(r, c);21 }22 }23 }24 return islands;25};