Number of Islands
Problem Statement
You are given an m x n 2D grid of characters where '1' represents land and '0' represents water. An island is a group of land cells connected 4-directionally (up, down, left, right) and is surrounded by water.
Return the number of islands in the grid.
Input
A 2D char array grid of '0' and '1' values. The border of the grid is implicitly surrounded by water.
Output
An integer: the count of distinct islands.
Constraints
- •
m == grid.length - •
n == grid[i].length - •
1 <= m, n <= 300 - •
grid[i][j] is '0' or '1'
Examples
Example 1
grid = [ ['1','1','0','0'], ['1','1','0','0'], ['0','0','1','0'], ['0','0','0','1'] ]
3Example 2
grid = [ ['1','1','1'], ['0','1','0'], ['1','0','1'] ]
3Learning Objectives
- See a 2D grid as an implicit graph where each land cell is a node with up to four neighbours.
- Use DFS or BFS to discover and 'sink' an entire connected component in one sweep.
- Understand why marking cells visited in-place (or with a visited set) prevents infinite loops and double counting.
Intuition
Think of the grid as a map. Every time you spot land you have not seen before, you have found a new island — so you increment your counter and then walk the entire island to mark every one of its cells as visited. That walk is a graph traversal: from a land cell you move to its land neighbours, and from those to theirs, until the whole connected blob is consumed.
The key realisation is that the outer double loop only starts a traversal at fresh land. Any land already swallowed by a previous traversal is now water (or marked), so it can never start a second island. That is what guarantees each island is counted exactly once.
Recognise the pattern: whenever a problem asks you to count or size connected regions in a grid, reach for grid DFS/BFS with in-place marking.
Common mistakes
- ×Forgetting to mark a cell visited *before* (or as) you enqueue it, causing the same cell to be processed many times and the BFS queue to explode.
- ×Counting diagonally-connected cells as one island — this problem is 4-directional only.
- ×Mutating the grid but the interviewer wanted it preserved; use a separate boolean[][] visited if the input must stay intact.
- ×Recursion depth: a 300x300 all-land grid can recurse ~90,000 deep and overflow the stack — mention BFS as the safe alternative.
Algorithm Explanation
- Initialise a counter to 0.
- Scan every cell (r, c) of the grid.
- When you find a '1', it is the seed of an undiscovered island: increment the counter and launch a traversal from (r, c).
- The traversal visits the seed and every land cell reachable from it, flipping each visited land cell to '0' (sinking it) so it is never revisited.
- After the full scan, the counter equals the number of islands.
Both DFS and BFS explore the same set of cells; they differ only in the order and in whether the call stack or an explicit queue holds the frontier.
Solutions
Solution 1: DFS (sink the island)
The most concise approach and the natural first answer in an interview. Prefer it when the grid is small-to-medium and stack depth is not a concern.
From each unvisited land cell, recurse into its four neighbours, sinking every land cell you touch. Recursion implicitly manages the frontier of cells still to explore.
Step-by-step
- Loop over all cells; on a '1', increment the count and call sink(r, c).
- sink returns immediately if (r, c) is out of bounds or is water — this single guard handles every edge of the grid.
- Otherwise mark the cell '0' and recurse in all four directions.
- Because the cell is sunk before recursing, the traversal cannot bounce back into it.
O(m · n)
O(m · n)
Every cell is visited once; worst-case recursion depth is the size of the largest island.
Java implementation
Solution 2: BFS (iterative queue)
Preferred when the grid is large enough that recursion could overflow the stack (e.g. a 300x300 solid-land grid). Trades the call stack for an explicit queue.
When you find fresh land, mark it visited and push it onto a queue. Repeatedly pop a cell and enqueue its unvisited land neighbours until the queue drains — that empties exactly one island.
Step-by-step
- On a '1', increment the count and start a BFS from that cell.
- Mark a cell '0' at the moment you enqueue it, never when you dequeue it — this is what keeps each cell out of the queue more than once.
- Use a fixed DIRECTIONS array to iterate the four neighbours cleanly.
O(m · n)
O(min(m, n))
Queue holds at most one BFS 'frontier', which is bounded by the smaller grid dimension.
Java implementation
Dry Run
Sample input
Trace the DFS on this 3x3 grid (rows and cols are 0-indexed):
Row 0: 1 1 0 Row 1: 0 1 0 Row 2: 1 0 1
| Scan cell | grid value | Action | Islands so far |
|---|---|---|---|
| (0,0) | 1 | New island → sink (0,0),(0,1),(1,1) | 1 |
| (0,1) | 0 | Already sunk, skip | 1 |
| (0,2) | 0 | Water, skip | 1 |
| (1,0) | 0 | Water, skip | 1 |
| (1,1) | 0 | Already sunk, skip | 1 |
| (2,0) | 1 | New island → sink (2,0) | 2 |
| (2,1) | 0 | Water, skip | 2 |
| (2,2) | 1 | New island → sink (2,2) | 3 |
The first sink swallows the connected L-shape of three cells, so scanning (0,1) and (1,1) later finds only water. The two lone corners each seed their own island. Final answer: 3.
Interview Tips
Start by explicitly stating the grid-as-graph insight and the sink-on-visit trick — interviewers want to hear why it counts each island once. Mention up front that you can either mutate the grid or keep a visited matrix, and ask which they prefer. If they hint at very large grids, pivot to BFS to avoid stack overflow. Finish by noting Union-Find as a third option, which shines when islands can merge dynamically (the follow-up below).
Likely follow-ups
- Number of Islands II — cells turn to land one at a time and you must report the island count after each addition (Union-Find).
- What if connectivity were 8-directional (including diagonals)? Extend the DIRECTIONS array.
- Return the size of the largest island instead of the count (see Max Area of Island).
- The grid is too large to fit in memory — how would you stream it row by row?
Similar Problems
Key Takeaways
- A grid is a graph: each cell is a node with up to four neighbours.
- Count components by starting a traversal only at unvisited seeds and consuming the whole component.
- Mark cells visited at enqueue time (BFS) or before recursing (DFS) to avoid reprocessing.
- Reach for BFS when recursion depth is a risk on large inputs.