MediumDepth-First SearchBreadth-First SearchMatrixUnion FindUpdated Sep 2026

200. Number of Islands

Asked at Amazon, Apple, Oracle, Uber and 7 more

Difficulty

Medium

Time

O(m × n)

Space

O(m × n)

Pattern

Depth-First Search

Companies

11

Problem

You are given a grid of '1's (land) and '0's (water). Count the islands.

An island is a group of land cells connected up, down, left or right — diagonals do not connect. Everything outside the grid counts as water.

Connected sideways, never diagonally

012012110110001answer = 2
The orange block is one island; the green cell touches it only at a corner, so it is a second island.

Constraints

  • ●m == grid.length, n == grid[i].length
  • ●1 <= m, n <= 300
  • ●grid[i][j] is '0' or '1'

Examples

Example 1
Inputgrid = [["1","1","0"],["1","1","0"],["0","0","1"]]
Output2
WhyThe 2x2 block of land in the top-left is one island, and the single land cell at the bottom-right is another.
Example 2
Inputgrid = [["1","0","1"]]
Output2
WhyThe water cell in the middle keeps the two land cells apart.
Example 3
Inputgrid = [["0","0"],["0","0"]]
Output0
WhyThere is no land, so there are no islands.

Asked At

11 companies
CompanyDifficulty
AmazonMediumView all Amazon questions →
AppleMediumView all Apple questions →
OracleMediumView all Oracle questions →
UberMediumView all Uber questions →
WalmartMediumView all Walmart questions →
Goldman SachsMediumView all Goldman Sachs questions →
TikTokMediumView all TikTok questions →
LinkedInMediumView all LinkedIn questions →
VisaMediumView all Visa questions →
AndurilMediumView all Anduril questions →
NVIDIAMediumView all NVIDIA questions →

How to Think About It

1

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.

2

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).

3

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.

4

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).

Scan, then sink

Scan cells left to right, top to bottomHit a '1'? count += 1Flood fill it: turn the island into '0'after the first flood fill000000001count = 1, and the scan continues to the last '1'
Every scan that finds fresh land starts one flood fill, and that fill erases the whole island so it is never counted twice.
ComplexityTime O(m × n)Space O(m × n)Each cell is visited once. The worst-case stack or queue is the whole grid when it is all land.

What Trips People Up in Real Interviews

1

Confusing DFS with BFS. Both work, but DFS is simpler to implement recursively. BFS uses a queue and is more complex for this problem.

2

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.

3

Forgetting that the grid can be empty. Return 0 if the grid has no rows or columns.

4

Not handling the case where the grid has no land (all water). Return 0.

5

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

O(m × n) time
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 count

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(m × n) time and O(m × n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Number of Islands?

Number of Islands is asked at Amazon, Apple, Oracle, Uber, Walmart, Goldman Sachs, TikTok, LinkedIn, Visa, Anduril, NVIDIA. 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.