Number of Islands
Last Updated: March 28, 2026
Understanding the Problem
We have a 2D grid of characters where '1' represents land and '0' represents water. Two land cells belong to the same island if they are adjacent horizontally or vertically (not diagonally). We need to count how many distinct islands exist in the grid.
If you think about it, this is really a connected components problem on a graph. Each '1' cell is a node, and there is an edge between two nodes if they are horizontally or vertically adjacent and both are '1'. The number of islands is simply the number of connected components in this implicit graph.
The key observation is: once we find any unvisited land cell, we can explore all cells connected to it (marking them as visited), and that entire connected group counts as one island. Then we move on and look for the next unvisited land cell.
Key Constraints:
1 <= m, n <= 300-- The grid can have up to 300 x 300 = 90,000 cells. An O(m n) solution is well within time limits. Even O(m n alpha(m n)) for Union Find is fine.grid[i][j]is'0'or'1'-- Binary values, no special parsing needed.- With m * n up to 90,000, standard DFS, BFS, or Union Find all work within these bounds.
Approach 1: DFS (Depth-First Search)
Intuition
The most natural way to think about this: scan the grid from top-left to bottom-right. Every time we hit a '1' that we haven't visited yet, we have discovered a new island. We then "flood fill" outward from that cell using DFS, marking every connected '1' as visited so we don't count it again. After the DFS finishes, we have fully explored one island. We increment our count and keep scanning.
The trick to keep things simple is modifying the grid in-place. When we visit a '1', we change it to '0'. This way, we don't need a separate visited array. Every cell we touch gets "sunk," so future scans skip over it.
Algorithm
- Initialize an island counter to 0.
- Iterate through every cell in the grid (row by row, column by column).
- When we find a cell with value
'1', increment the island counter. - Run DFS from that cell: mark the current cell as
'0', then recursively visit all four neighbors (up, down, left, right) that are'1'. - After scanning all cells, return the island counter.
Example Walkthrough
Code
- Time Complexity: O(m * n). We visit every cell in the grid exactly once. The outer loop touches each cell, and DFS only visits cells that are still '1'. Once a cell is sunk to '0', it is never visited again.
- Space Complexity: O(m n). In the worst case (entire grid is land), the DFS recursion stack can go as deep as m n. In practice, the stack depth is proportional to the size of the largest island.
The DFS approach is O(m * n) in time, which is optimal. But the recursion stack can be a problem for very large all-land grids (up to 90,000 levels deep). What if we replaced the recursion with an explicit queue?
Approach 2: BFS (Breadth-First Search)
Intuition
The BFS approach works on exactly the same principle as DFS: find an unvisited '1', explore all connected '1' cells, count that as one island. The difference is mechanical. Instead of using the system call stack (recursion), we use an explicit queue.
BFS avoids the stack overflow risk that DFS has on very large islands. It explores in layers outward from the starting cell, which means the queue size at any moment is bounded by the perimeter of the current exploration front, not the total size of the island.
BFS and DFS are two ways to traverse the same implicit graph. Both visit every cell connected to the starting cell exactly once. Sinking cells as we enqueue them ensures no cell is visited twice, and exploring all four directions ensures we reach every cell in the connected component.
The key implementation detail is sinking the cell when we enqueue it, not when we dequeue it. If you wait until dequeue, the same cell can be added to the queue multiple times by different neighbors, wasting time and memory.
Algorithm
- Initialize an island counter to 0.
- Iterate through every cell in the grid.
- When we find a
'1', increment the island counter, sink the cell to'0', and add it to a queue. - While the queue is not empty, dequeue a cell, and for each of its four neighbors that is
'1', sink it to'0'and enqueue it. - After scanning all cells, return the island counter.
Example Walkthrough
Code
- Time Complexity: O(m * n). Same as DFS. Every cell is visited at most once across all BFS calls.
- Space Complexity: O(min(m, n)). The queue holds at most the cells along the BFS frontier. In the worst case (all land), the largest frontier is bounded by min(m, n).
Both DFS and BFS modify the input grid in-place. What if the interviewer says "don't modify the input"? We can use Union Find to track connected components without touching the grid.
Approach 3: Union Find (Disjoint Set Union)
Intuition
Union Find offers a completely different angle. Instead of "exploring" islands via traversal, we build them up incrementally. We scan the grid once. For every '1' cell, we check its right neighbor and its bottom neighbor. If a neighbor is also '1', we union the two cells into the same set.
At the end, the number of distinct sets that contain '1' cells is the number of islands. We track this with a count that starts at the total number of '1' cells and decrements by one every time a successful union merges two previously separate sets.
This approach does not modify the input grid. It also generalizes well to the dynamic version of the problem (Number of Islands II) where land cells are added one at a time.
Union Find maintains a forest of trees where each tree represents a connected component. The find operation traces a cell to the root of its tree (with path compression flattening the tree for future lookups). The union operation merges two trees by attaching the smaller one under the larger one (union by rank), keeping the tree shallow.
By only checking right and down neighbors, we ensure every pair of adjacent land cells is unioned exactly once. Since we scan left-to-right, top-to-bottom, any pair (i,j) and (i,j+1) or (i,j) and (i+1,j) is encountered when we process the earlier cell.
Algorithm
- Count the total number of
'1'cells. This is our initial island count (each'1'starts as its own island). - Initialize a Union Find structure where each
'1'cell is its own parent. - Scan the grid. For each
'1'cell, check the cell to its right and the cell below it. - If a neighbor is also
'1', union the current cell with the neighbor. If the union merges two previously separate sets, decrement the island count. - Return the final island count.
Example Walkthrough
Code
- Time Complexity: O(m n alpha(m n)). We scan every cell once and perform at most 2 union operations per cell. Each find/union with path compression and union by rank takes amortized O(alpha(N)) time. For all practical purposes, alpha(N) < 5, so this is effectively O(m n).
- Space Complexity: O(m n). The parent and rank arrays each have m n entries. Unlike DFS/BFS, this approach does not modify the input grid.