How do you approach Number of Islands?

Iterate through the grid. When you find a '1', you've found an island.

What is the time complexity of Number of Islands?

Time complexity: O(m n). Space complexity: O(m n) for recursion stack in worst case.

What are common mistakes on Number of Islands?

Building the adjacency list in one direction on an undirected graph. Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest. Ignoring self-loops and parallel edges when the constraints allow them.

gitGood.dev

← Back to problems

Number of Islands

MediumData Structures

Description

Given an `m x n` 2D binary grid `grid` which represents a map of `'1'`s (land) and `'0'`s (water), return the number of islands. An **island** is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1

Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]

Output: 1

Example 2

Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ]

Output: 3

Constraints

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

Number of Islands: approach, complexity and pitfalls

A medium graphs problem, graded against 6 test cases (3 of them hidden).

The pattern: Graphs

Nodes and edges - traversal, connectivity, cycles, and shortest paths.

Reach for it when you see: Explicit edges, a grid treated as a graph, or dependencies between items.

More Graphsproblems →

If you are stuck

Show the 3-step hint ladder

Iterate through the grid. When you find a '1', you've found an island.
Use DFS or BFS to mark all connected land cells as visited.
Count how many times you start a new DFS/BFS.

The optimal approach

Show the approach: DFS

Iterate through the grid. When finding a '1', increment the island count and use DFS to mark all connected land cells as '0' (visited).

Time: O(m * n)
Space: O(m * n) for recursion stack in worst case

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Graphs mistakes

These apply to the pattern as a whole, not just this problem.

Building the adjacency list in one direction on an undirected graph.
Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest.
Ignoring self-loops and parallel edges when the constraints allow them.