Number of Islands
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.
This is 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 the number of connected components in this implicit graph.
Once we find any unvisited land cell, we can explore all cells connected to it and mark them visited. That entire connected group counts as one island. We then move on and look for the next unvisited land cell.
Key Constraints:
1 <= m, n <= 300means the grid can have up to 300 x 300 = 90,000 cells. An O(m n) solution is well within time limits, and so is the O(m n alpha(m n)) of Union Find.grid[i][j]is'0'or'1', so there are no other characters to handle. DFS, BFS, and Union Find all fit within these bounds.
Approach 1: DFS (Depth-First Search)
Intuition
Scan the grid from top-left to bottom-right. The first '1' we reach that has not been visited yet belongs to a new island. We flood fill outward from that cell using DFS, marking every connected '1' as visited so it is not counted again. Once the DFS finishes, one island has been fully explored. We increment the count and keep scanning.
To avoid a separate visited array, we modify the grid in-place. When we visit a '1', we change it to '0'. Every cell we touch gets "sunk," so later iterations of the scan 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 runs in O(m * n) time, which is optimal. Its weakness is the recursion stack: on a grid that is entirely land, the recursion can go 90,000 levels deep and overflow the call stack. The next approach replaces the recursion with an explicit queue, which moves the traversal state to the heap.
Approach 2: BFS (Breadth-First Search)
Intuition
BFS uses the same principle as DFS: find an unvisited '1', explore all connected '1' cells, count that group as one island. The difference is mechanical. Instead of the system call stack (recursion), it uses an explicit queue, which removes the stack overflow risk on large islands. BFS explores in layers outward from the starting cell, so the queue holds at most the cells along the current frontier rather than the whole island.
Sink each cell when it is enqueued, not when it is dequeued. If a cell is only sunk on dequeue, it can still read as '1' while sitting in the queue, so two different neighbors can both enqueue it before either is processed. The cell then gets visited twice, and the queue can hold duplicate entries that, in the worst case, push memory toward O(m * n) instead of O(min(m, n)). Sinking on enqueue guarantees each cell enters the queue exactly once.
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 to mark visited cells. When the grid must stay unchanged, Union Find tracks connected components in a separate data structure and leaves the grid alone.
Approach 3: Union Find (Disjoint Set Union)
Intuition
Union Find builds islands up incrementally instead of exploring them by traversal. Scan the grid once. For every '1' cell, check its right neighbor and its bottom neighbor. If a neighbor is also '1', 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 union merges two previously separate sets.
This approach leaves the input grid unchanged. It also extends to the dynamic version of the problem (Number of Islands II), where land cells are added one at a time and re-running a full traversal after each addition would be wasteful.
Checking only the right and bottom neighbors unions every adjacent pair exactly once. The grid is scanned left-to-right, top-to-bottom, so any horizontal pair (i,j)-(i,j+1) and any vertical pair (i,j)-(i+1,j) is handled when the earlier cell is processed. The left and top neighbors are skipped because the edge to them was already created from the other side, which avoids redundant union calls.
The count stays accurate because it decrements only inside union, and only when the two roots differ. Two cells in the same island that are reached through a longer path are already in one set by the time their direct edge is examined, so that union finds equal roots and leaves the count alone.
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.