Number of Islands
Asked at Amazon, Apple, Oracle, Uber, Walmart
Problem
Given a 2D grid of "1"s (land) and "0"s (water), count the number of islands. An island is formed by connecting adjacent land cells horizontally or vertically. This is one of the most common grid traversal problems.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
| Apple | Medium | View all Apple questions → |
| Oracle | Medium | View all Oracle questions → |
| Uber | Medium | View all Uber questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
When you find an unvisited "1", you've found a new island. Increment your count and flood-fill (DFS or BFS) to mark all connected "1"s as visited.
Why flood-fill works: once you find an island, you need to mark all its cells so you don't count them again. Set visited cells to "0" (or use a visited set).
DFS vs BFS: DFS is simpler to write recursively (4 recursive calls). BFS uses a queue — safer for very large grids where recursion might overflow.
Visual walkthrough for grid:
[["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]]
- Scan (0,0): "1" found. Count=1. DFS marks (0,0),(0,1),(1,0),(1,1) as "0".
- Scan (0,2): "0". Skip.
- Scan (2,2): "1" found. Count=2. DFS marks (2,2).
- Scan (3,3): "1" found. Count=3. DFS marks (3,3),(3,4).
Result: 3 islands.
Union-find alternative: treat each "1" as a node. Union adjacent "1"s. Count unique roots. Better for dynamic grids (adding/removing land).
Optimal Approach
Step 1: Iterate through every cell.
Step 2: When you find a "1":
- Increment island count
- Start DFS/BFS from that cell
- Mark all connected "1"s as "0" (visited)
Step 3: Continue scanning.
DFS flood-fill: from (r, c), recursively visit all 4 neighbors that are "1". Mark each as "0" when visited.
The key insight: you only start DFS from unvisited "1"s. Each DFS marks an entire island. The count of DFS calls = number of islands.
Time: O(m × n). Space: O(m × n) for recursion stack (worst case: all land).
What Trips People Up in Real Interviews
Confusing DFS with BFS. Both work, but DFS is simpler to implement recursively. BFS uses a queue and is more complex for this problem.
Not marking visited cells. If you don't mark cells as visited, you'll count the same island multiple times. Mark by setting the cell to '0' or using a visited set.
Forgetting that the grid can be empty. Return 0 if the grid has no rows or columns.
Not handling the case where the grid has no land (all water). Return 0.
Incrementing the count inside DFS instead of after it. The count should increment when you FIND an unvisited "1", not for each cell visited by DFS — incrementing inside causes overcounting.
Solution Code
def numIslands(grid):
def dfs(r, c):
if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] != '1':
return
grid[r][c] = '0'
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
count = 0
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == '1':
dfs(r, c)
count += 1
return countFrequently Asked Questions
What is the Number of Islands problem?
Given a 2D grid of "1"s (land) and "0"s (water), count the number of islands. An island is formed by connecting adjacent land cells horizontally or vertically. This is one of the most common grid traversal problems.
How do you solve Number of Islands?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Number of Islands?
Number of Islands is asked at Amazon, Apple, Oracle, Uber, Walmart. It is a medium difficulty problem.
What are common mistakes on Number of Islands?
- Confusing DFS with BFS. Both work, but DFS is simpler to implement recursively. BFS uses a queue and is more complex for this problem.
- Not marking visited cells. If you don't mark cells as visited, you'll count the same island multiple times. Mark by setting the cell to '0' or using a visited set.
- Forgetting that the grid can be empty. Return 0 if the grid has no rows or columns.
- Not handling the case where the grid has no land (all water). Return 0.
- Incrementing the count inside DFS instead of after it. The count should increment when you FIND an unvisited "1", not for each cell visited by DFS — incrementing inside causes overcounting.