Number of Islands
Maintained by Vikas D, software engineer
You are handed a rectangular grid where every cell holds either the character '1' for land or '0' for water. A group of land cells that are joined to each other forms a single island. Two land cells count as joined when they sit directly next to each other in a vertical or horizontal direction. Cells that meet only at a corner are not joined.
Your job is to report how many distinct islands the grid contains. Water cells never belong to any island, and the area outside the grid is treated as water, so islands along the edges still count as fully surrounded.
The same land cell can never belong to two islands at once. Once you decide which island a cell is part of, every other land cell reachable from it through up, down, left, or right moves belongs to that same island. The answer is the number of these connected groups.
Examples
The three '1's in the top-left corner all touch edge to edge, so they form one island. The lone '1' in the bottom-right corner touches no other land, so it forms a second island. Total: 2.
Each '1' sits in a checkerboard pattern where its only land neighbours are diagonal, which does not count as connected. So all five land cells are isolated and each is its own island.
Every cell is water, so there are no islands.
Constraints
- m == grid.length, n == grid[0].length
- 1 <= m, n <= 300
- Every cell is the character '0' or '1' (note: these are string characters, not integers)
- Diagonal contact does not connect two land cells; only up, down, left, and right do
Visible test cases
- numIslands([["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]) == 1
- numIslands([["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]) == 3
- numIslands([["0","0","0"],["0","0","0"]]) == 0
- numIslands([["1","0","1"],["0","1","0"],["1","0","1"]]) == 5
- numIslands([["1"]]) == 1
- numIslands([["1","1"],["1","1"]]) == 1
Hints
Hint 1
Walk the grid cell by cell. The first time you hit a land cell that you have not seen before, you have found a brand-new island, so add one to your count.
Hint 2
After finding that new island, expand outward from it and visit every land cell reachable through up/down/left/right moves, marking each as visited so the outer scan never starts a second island from the same landmass.
Hint 3
Use depth-first or breadth-first search to flood the island. Flipping each visited land cell to '0' in place is a clean way to mark it without a separate visited grid, as long as you are allowed to modify the input.
Approaches
Flood fill with DFS or BFS
Time O(m * n) · Space O(m * n)Scan every cell. Each unvisited '1' starts a new island; from there, traverse all connected land and mark it visited so it is counted only once.
- Initialize a counter to 0.
- Loop over every cell (i, j) of the grid in row-major order.
- When you reach a cell equal to '1', increment the counter because this is the entry point of an island not yet counted.
- Run a DFS or BFS from (i, j): repeatedly take a land cell, set it to '0' to mark it visited, and push its four orthogonal neighbours that are still '1'.
- Continue the traversal until no connected land remains, then resume the outer scan.
- Return the counter after the full grid has been scanned.
Union-Find (disjoint set)
Time O(m * n * alpha(m * n)) · Space O(m * n)Treat each land cell as a node and union it with its right and down land neighbours. The number of distinct sets among land cells is the island count.
- Create a disjoint-set structure with one element per cell, plus a count of land cells.
- For each land cell, union it with its right neighbour and its lower neighbour when those are also land, decrementing the count on each successful merge.
- After processing all cells, the remaining count of distinct land roots is the number of islands.
- Path compression and union by rank keep each operation nearly constant time.
Common mistakes
- Comparing against the number 1 instead of the string '1'. The grid holds character cells, so grid[i][j] === 1 is always false.
- Counting diagonal neighbours as connected. Only the four orthogonal directions join land cells; including diagonals overcounts merged islands as one.
- Forgetting to mark cells visited, which sends DFS or BFS into infinite revisits and can blow the stack or hang.
- Recursive DFS overflowing the call stack on large near-solid grids up to 300 x 300; an explicit stack or BFS queue avoids that.
- Reading grid[0].length without first checking the grid is non-empty, though the constraints guarantee at least a 1 x 1 grid.
Follow-up variations
- Return the size of the largest island instead of the count (see the max-area-of-island variant).
- Allow diagonal connections (8-directional adjacency) and recount.
- Handle a grid too large to fit in memory by streaming rows and merging islands across a sliding boundary.
- Support a stream of land cells being added one at a time and report the island count after each addition, which points squarely at Union-Find.
- Count the perimeter of the islands rather than their number.