Coding · Graphs and grids
Number of Islands
- Appears on company lists
- Medium
- 1 source
Company-tagged lists or prep guides name it; no candidate write-up was found.
Solve it in the playground, with tests
A grid holds 1 for land and 0 for water. An island is a group of land cells joined through shared sides (up, down, left or right, never diagonally), and you must return how many islands the grid contains. For the grid [[1, 1, 0, 0], [0, 1, 0, 1], [1, 0, 0, 1]] the answer is 3. The grid is a rectangle of up to 300 rows and 300 columns.
Restated in our own words, not a quote from Apple or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: do diagonal neighbours count as connected, or only the four side neighbours? Are the cells numbers or the characters "0" and "1"? Is every row the same length? Can the grid be empty, or have empty rows? And am I allowed to change the input grid, or must it come back untouched?
I would assume four-way connection, rectangular grids, and numbers 0 and 1. An empty grid has zero islands. I will not modify the input; I will keep a separate visited table, and mention that overwriting land with water is a common memory-saving alternative if mutation is allowed.
Brute force
Say the obvious answer and why it is too slow.
One naive approach floods outward from every land cell, collects the cells it reaches, and counts the distinct islands by remembering some canonical cell of each, such as the smallest index. Nothing is remembered between floods, so an island with s cells is explored s times, each time touching s cells.
That makes the work O(s²) for one island and up to O((m times n)²) for a grid dominated by a single island. A 300 by 300 grid of all land has 90,000 cells, so the total is around eight billion cell visits. A cheaper wrong idea is to count land cells that have no land neighbour above or to the left, which miscounts any U-shaped island because its two arms look like separate starts.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O((m · n)²)
- Time
- O(m · n)
- Space
- O(m · n)
Each island is a connected component of land cells, so the question is "how many components", which is the standard flood-fill problem. Scan the grid in order. When you meet a land cell that has not been seen, you have found an island you have not counted yet, because every island you counted earlier has already been fully marked. Count it, then flood-fill from that cell and mark every connected land cell as seen so the scan will skip them.
The invariant is: after each flood, all cells of that island are marked, so an unseen land cell found later must belong to a new island. That is the full proof, and it is also why you can stop worrying about double counting. The flood itself can be depth-first or breadth-first; both visit exactly the same set of cells.
The detail that separates a working solution from one that crashes is the stack. A recursive flood on a 300 by 300 snake-shaped island recurses up to 90,000 levels deep, which overflows the JavaScript call stack. So I use an explicit stack in a loop and mark a cell as seen when I push it, not when I pop it. Marking at push time keeps each cell in the stack at most once.
Every cell is scanned once and examined by its four neighbours at most four times, so the time is O(m times n), and the seen table and stack use O(m times n) memory. Out loud: "connected components by grid flood fill, one count per unseen land cell."
Walk it through
A dry run on the example, step by step.
| Scan reaches | State of the cell | Islands | Flood marks |
|---|---|---|---|
| (0,0) | land, unseen: new island | 1 | (0,0) (0,1) (1,1) |
| (0,1) to (1,2) | seen or water: skip | 1 | none |
| (1,3) | land, unseen: new island | 2 | (1,3) (2,3) |
| (2,0) | land, unseen: new island | 3 | (2,0) |
| (2,1) to (2,3) | water or seen: skip | 3 | none |
The grid has three rows and four columns: land at (0,0), (0,1), (1,1), (1,3), (2,0) and (2,3). The scan reaches (0,0) first. It is land and unseen, so the count becomes 1 and the flood marks (0,0), then (0,1), then (1,1). Those three cells are one island.
The scan then passes (0,1) through (1,2); each of those is already marked or water, and the count stays at 1. At (1,3) it finds fresh land, so the count becomes 2, and the flood takes (1,3) and (2,3). Finally it reaches (2,0): its only neighbours, (1,0) and (2,1), are water. The cell (1,1) touches it only diagonally, and diagonals do not count, so this is a third island. The rest of the scan finds nothing new, and the answer is 3, as the last row of the table shows.
The code
Runnable JavaScript, checked against test cases.
function numIslands(grid) {
const rows = grid.length;
const seen = grid.map((row) => row.map(() => false));
const steps = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let islands = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < grid[r].length; c++) {
if (grid[r][c] !== 1 || seen[r][c]) continue;
islands++;
seen[r][c] = true;
const stack = [[r, c]];
while (stack.length > 0) {
const [row, col] = stack.pop();
for (const [dr, dc] of steps) {
const nr = row + dr;
const nc = col + dc;
const inside = nr >= 0 && nr < rows && nc >= 0 && nc < grid[nr].length;
if (inside && grid[nr][nc] === 1 && !seen[nr][nc]) {
seen[nr][nc] = true;
stack.push([nr, nc]);
}
}
}
}
}
return islands;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
An empty grid has no rows, so the outer loop never runs and the answer is 0. A grid with empty rows has no columns to scan, which gives 0 as well. A grid of all water gives 0, a grid of all land gives 1, and a single land cell gives 1. A checkerboard has every land cell alone, because its neighbours are diagonal, so the count equals the number of land cells.
Non-square grids work because the bounds checks use the row count for the row index and the length of that row for the column index. A very long snake does not blow the stack because the flood is iterative. A U-shaped island is counted once: the first arm starts the flood and the flood reaches the second arm through the bottom. Cells on the border are protected by the bounds test, which runs before any read of the grid.
Follow-ups to expect
Where the interviewer pushes next.
- How would you count islands if the grid arrives as a stream of changes, one cell turning to land at a time?
- How would you find the area of the largest island?
- How would you solve it with union-find, and when is that the better tool?
- How would you count distinct island shapes, treating translated copies as equal?
- What changes if diagonals count as connected?
Where candidates slip
The mistakes this problem punishes.
The most common slip is recursion depth: a recursive flood passes the small tests and then crashes on a large snake of land. The next is forgetting to mark visited cells, which makes the flood loop forever between two neighbours, or marking only when popping, which pushes the same cell many times.
Candidates also count land cells instead of components, let diagonals connect cells, or mix up rows and columns in the bounds check, which only shows on a non-square grid. Another is mutating the input without saying so. And a classic interview slip is writing the flood and forgetting to increment the island count exactly once per flood, at the place where it starts.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.