Skip to content

Practice Number of Islands

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Medium#200
LeetCode Problem

Number of Islands

Problem Statement

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.

Source: Number of Islands on LeetCode. Use the original task for its coding environment and submissions.

Examples

# 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'.

How to solve Number of Islands

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

Each island is one connected component of land cells. Scanning the grid and launching a flood fill from every unvisited land cell counts a component exactly once, because the fill marks every cell of that island before the scan moves on.

Why brute force is not enough

Testing connectivity between every pair of land cells, or re-exploring an island from each of its cells, is quadratic in the number of cells. A 300 by 300 grid has 90000 cells, so pairwise work approaches 8 * 10^9 operations.

Approach

  1. Iterate over every cell in row-major order.
  2. When you find a land cell that has not been visited, increment the island count and start a traversal from it.
  3. The traversal (breadth-first with a queue or depth-first with an explicit stack) visits the four orthogonal neighbors, skipping out-of-bounds cells, water, and already-visited cells. Mark a cell visited when it is discovered, before it is expanded.
  4. Marking can overwrite the land cell with water in place or use a separate visited matrix if the input must be preserved.
  5. After the scan, the count equals the number of islands.

Walkthrough of Example 2

grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] → 3

  1. Row 0, column 0 is land and unvisited: the count becomes 1. The fill marks (0,0), (0,1), (1,0), and (1,1).
  2. The scan continues over row 0 and row 1; the remaining cells are water or already marked.
  3. Row 2, column 2 is land: the count becomes 2. Its four neighbors are all water, so the fill marks only that cell.
  4. Row 3, column 3 is land: the count becomes 3. The fill marks (3,3) and (3,4).
  5. No further land cells remain; the answer is 3.

Time and space

Time O(m * n) · Space O(m * n). Every cell is scanned once and enters a traversal at most once, where m and n are the grid dimensions; the queue or stack can hold up to all land cells in the worst case.

Interview pitfalls

  • Recursive depth-first search on a 300 by 300 all-land grid recurses up to 90000 frames deep and can overflow the call stack; use breadth-first or an explicit stack.
  • Marking a cell visited when dequeued instead of when enqueued, which enqueues the same cell many times and inflates the queue.
  • Counting diagonal neighbors as connected; only horizontal and vertical adjacency forms an island.
  • The grid holds characters, not integers; comparing against the integer 1 silently finds no land.
  • Mutating the input grid without saying so; interviewers may want the input preserved.

Follow-up questions interviewers ask

  • How would you solve it with union-find, and when would that be preferable?
  • Islands are added one cell at a time; report the count after each addition (Number of Islands II).
  • Count distinct island shapes, treating translations as identical.

Further reading on the technique: Flood fill

Related LeetCode Problems

Practice more problems similar to Number of Islands.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.