Number of Islands
Count the separate patches of land in a grid of 1s and 0s. The go-to problem for flood fill with DFS or BFS on a 2D grid. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given a 2D grid grid where 1 is land and 0 is water. Two land cells belong to the same island if they share an edge (up, down, left, or right). Diagonal neighbors are not connected.
Return the number of islands. Everything outside the grid counts as water.
Example 1
- Input
- grid = [ [1, 1, 0, 0, 1], [1, 0, 0, 1, 1], [0, 0, 1, 0, 0], [1, 0, 0, 0, 1] ]
- Output
- 5
The top-left L-shape, the top-right L-shape, the center cell, and the two bottom corners are each their own island.
Example 2
- Input
- grid = [[1, 0, 1], [0, 1, 0], [1, 0, 1]]
- Output
- 5
The cells only touch diagonally, so none of them join up.
Example 3
- Input
- grid = [[0, 0], [0, 0]]
- Output
- 0
Constraints
- 1 ≤ grid.length, grid[i].length ≤ 300
- grid[i][j] is 0 or 1.
Practice
Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Number of Islands in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Number of Islands
Pattern: Flood fill (DFS/BFS on a grid)
Think of the grid as a graph: every land cell is a node, and it has an edge to each land cell directly above, below, left, or right of it. An island is then a connected component, and the question becomes "how many components does this graph have?"
The standard way to count components: scan every cell, and whenever you hit land you haven't visited yet, you've found a new island. Increment the count, then flood outward from that cell and mark every land cell you can reach as visited. When the flood stops, that whole island is accounted for, and the scan will skip it from then on.
You don't need a separate visited set. Overwriting a land cell with 0 as you visit it ("sinking" it) does the same job in O(1) extra space per cell.
Approach 1: Union-find
Give each land cell its own set, then union it with its land neighbors to the right and below. The answer is the number of sets that remain. It works and generalizes to a grid where land is added over time, but it is more code than a flood fill for a static grid.
Time O(m · n · α(m · n)) · Space O(m · n)
Approach 2: Recursive DFS
Scan the grid; on each unvisited land cell, add one and call a recursive sink(r, c) that sets the cell to 0 and recurses into its four neighbors. Short and clear, but the recursion can go as deep as the number of cells in one island, which overflows the default Python stack on a large solid island.
Time O(m · n) · Space O(m · n) call stack in the worst case
Approach 3: Iterative flood fill with an explicit stack
Same scan, but replace recursion with your own stack:
- Loop over every cell. Skip water.
- On land, increment the count, set the cell to 0, and push it.
- While the stack isn't empty, pop a cell and look at its four neighbors. Any neighbor that is in bounds and still land gets set to 0 and pushed.
Setting a cell to 0 when you push it, not when you pop it, guarantees each cell is pushed at most once. Swapping the stack for a queue gives BFS with the same cost.
Time O(m · n) · Space O(m · n) in the worst case
| Approach | Time | Space |
|---|---|---|
| Union-find | O(m · n · α(m · n)) | O(m · n) |
| Recursive DFS | O(m · n) | O(m · n) call stack in the worst case |
| Iterative flood fill with an explicit stack | O(m · n) | O(m · n) in the worst case |
Solution code
Try the practice editor first. Both solutions pass every test above.
Number of Islands solution in Python
def num_islands(grid: list[list[int]]) -> int:
rows, cols = len(grid), len(grid[0])
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != 1:
continue
count += 1
grid[r][c] = 0
stack = [(r, c)]
while stack:
cr, cc = stack.pop()
for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 0
stack.append((nr, nc))
return countNumber of Islands solution in JavaScript
function numIslands(grid) {
const rows = grid.length;
const cols = grid[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let count = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] !== 1) continue;
count++;
grid[r][c] = 0;
const stack = [[r, c]];
while (stack.length) {
const [cr, cc] = stack.pop();
for (const [dr, dc] of dirs) {
const nr = cr + dr;
const nc = cc + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
grid[nr][nc] = 0;
stack.push([nr, nc]);
}
}
}
}
}
return count;
}Common mistakes
- Counting diagonal neighbors as connected. Only the four edge-sharing directions count.
- Marking a cell visited only when it is popped, so the same cell gets pushed many times and the work blows up.
- Checking `grid[r][c]` before checking that `r` and `c` are in bounds. In Python, a negative index silently wraps around to the other side of the grid.
- Using recursive DFS in Python on a big island and hitting the recursion limit.
- Mutating the input without saying so. If the caller needs the grid afterward, use a visited set or restore it.
What interviewers look for
Name the reduction early: "land cells are nodes, edges join neighbors, and I'm counting connected components." That tells the interviewer you see the general graph problem and not just a grid trick.
Then say how you'll mark visited cells and ask whether mutating the grid is acceptable. Mention recursion depth if you write DFS recursively; offering the iterative version unprompted is a strong signal. Before finishing, trace a tiny case where an island bends back on itself (like a U shape) to show the flood reaches every cell.
Follow-up questions
What if land is added one cell at a time and you need the island count after each addition?
Re-running the flood fill each time costs O(m · n) per addition. Use union-find instead: when a cell becomes land, add a new set (count + 1) and union it with any land neighbors, subtracting 1 for each union that actually merges two sets. Each addition is then nearly O(1).
How would you find the size of the largest island?
Same flood fill, but count how many cells you sink during each flood and keep the maximum. Nothing else changes.
What if the grid is too large to fit in memory?
Process it row by row and keep union-find labels only for the current and previous rows. Components that stop touching the current row are finished and can be counted and discarded, so memory stays proportional to the row width.
Companies that ask Number of Islands
Number of Islands is tagged by 189 companies in our interview dataset. The score shows how often it comes up at each company.
- Wixcom100%
- Anduril Industries100%
- Arrow Electronics100%
- Icertis100%
- Rapid7100%
- Lucid Motors100%
- Zenefits100%
- Activecampaign100%
- Greenlight100%
- Moloco100%
- Rivian100%
- Hive100%
- Okx100%
- Snap98.6%
- Roche98%
- TikTok97.3%
- Walmart Labs96.9%
- Crowdstrike96.8%
- Siemens96.6%
- Chamberlain Group94%
- Tinkoff93.8%
- AMD93.8%
- Equipmentshare92%
- Qualcomm90.5%
and 165 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required