You are given an m x n grid where each cell is either "1" (land) or "0" (water), as a 2-D array of single-character strings.
An island is a maximal group of "1" cells joined 4-directionally (up, down, left, right — not diagonally), bounded by water or the edge of the grid. Assume the grid is surrounded by water on all sides.
Return the number of distinct islands.
Example
All the land cells are connected horizontally or vertically into a single component.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 300
- grid[i][j] is "0" or "1".
Intuition
We need to count connected groups of land. The most literal approach: every time we want to know which cells belong together, re-scan from each land cell and gather everything reachable from it — but that re-walks the same component over and over, once per cell it contains.
function numIslands(grid) {
const rows = grid.length, cols = grid[0].length;
const label = Array.from({ length: rows }, () => new Array(cols).fill(0));
let next = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] !== '1' || label[r][c] !== 0) continue;
next++;
// Re-flood from here to paint the whole component with this label...
const stack = [[r, c]];
label[r][c] = next;
while (stack.length) {
const [cr, cc] = stack.pop();
for (const [nr, nc] of [[cr+1,cc],[cr-1,cc],[cr,cc+1],[cr,cc-1]]) {
if (nr<0||nc<0||nr>=rows||nc>=cols) continue;
if (grid[nr][nc] !== '1' || label[nr][nc] !== 0) continue;
label[nr][nc] = next;
stack.push([nr, nc]);
}
}
}
}
return next;
}Maintaining the label grid is busywork — we never actually need the labels, only the count. Can we do better?
The key observation: the grid is a graph in disguise — each land cell is a vertex, each pair of orthogonally adjacent land cells an edge — and counting islands is just counting connected components. So scan once; the first time we touch an un-sunk land cell, that's a new island, and a single flood fill (DFS) sinks its entire component to "0" so it's never recounted. The grid itself doubles as the visited marker.
The walk happens on the 2-D board, so the diagram is a gridWalkthrough. Sunk cells are marked; the cursor is the cell the flood is currently sinking. Walking it through:
scan + flood-fill — sinking each island so the next scan can't recount it
The first land cell is the start of island #1. Launch a flood fill from it.
The flood reaches every cell connected to (0,0) — the L-shaped trio — sinking each to '0'. Island #1 is now erased from the grid.
The scan continues from where it left off and finds (0,4), still land: island #2. Flood sinks it and (1,4) below it.
Lower down, (2,2) is the seed of island #3; the flood sinks the connected (3,2) and (3,3).
The rest of the scan finds only water. Three flood-fills launched, so three islands. The diagonal gap between island #2 and the rest never merged them — adjacency is orthogonal only.
Optimization
Flood fill (iterative DFS)
Scan every cell. When you reach a piece of land ("1") that hasn't been claimed yet, that's a brand-new island — increment the count, then flood-fill its entire connected component so it's never counted again.
The flood fill walks to the four orthogonal neighbours, sinking each visited land cell to "0" so it can't be revisited (this doubles as the "visited" marker, using the grid itself). An explicit stack is used instead of recursion so a single sprawling all-land grid can't overflow the call stack.
O(m·n) time — each cell is pushed and popped at most once — and O(m·n) space in the worst case for the stack (a grid that is entirely land).
function numIslands(grid) {
const rows = grid.length;
const cols = grid[0].length;
// Sink the whole component reachable from (sr, sc) so it can't be recounted.
const sink = (sr, sc) => {
const stack = [[sr, sc]];
grid[sr][sc] = "0"; // mark visited as we push, not as we pop
while (stack.length > 0) {
const [r, c] = stack.pop();
// Visit the four orthogonal neighbours.
for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
if (grid[nr][nc] !== "1") continue;
grid[nr][nc] = "0"; // sink before pushing — no cell enters twice
stack.push([nr, nc]);
}
}
};
let islands = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
// First land cell of an unseen component: a new island.
if (grid[r][c] === "1") {
islands++;
sink(r, c);
}
}
}
return islands;
}Complexity analysis
Time complexity: O(m·n). Here's why:
- The outer scan visits each of the
m·ncells once. - The flood fills, summed over all islands, touch each land cell exactly once (a cell is sunk the first time it's reached and never re-entered).
Every cell is handled a constant number of times, so the total is O(m·n).
Space complexity: O(m·n). Here's why:
- The explicit flood-fill stack can hold up to
O(m·n)cells when the grid is one giant island. - No separate visited grid is allocated — sinking land to
"0"reuses the input.
So the extra space is O(m·n) in the worst case (a fully-land grid); the input grid is mutated rather than copied.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| grid = 0 | 0 | A single water cell — no islands. |
| grid = 111 | 1 | A single row of connected land is one island. |
| grid = 1 1 1 | 1 | A single column of connected land is one island. |
| grid = 10101 01010 10101 | 8 | Diagonal-only adjacency must NOT merge cells — every land cell stands alone. |
| grid = 1101 1001 0000 1111 | 3 | Three components: the top-left L, the lone top-right pair, and the bottom strip. |
Try it yourself
Write your solution against the real judge before checking the reference.