Amazon · Coding 5 of 5

Number of Islands

Count the groups of connected land cells in a grid.

MediumGraphBFSMatrixBest: O(m·n) time · O(m·n) worst case space

Practice question: an editorial practice prompt, not a claim that Amazon asks this exact question. Interviews vary by role, level, team, and location.

Problem

Problem statement

You are given an m × n grid where "1" is land and "0" is water. An island is a group of land cells connected horizontally or vertically — not diagonally. Return the number of islands.

Treat everything outside the grid as water.

Examples

Example 1
Input
grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output
3

Why: The top-left block, the single centre cell, and the bottom-right pair.

Example 2
Input
grid = [
  ["1","0","1"],
  ["0","1","0"]
]
Output
3

Why: Diagonal neighbours do not connect.

Constraints

  • 1 ≤ m, n ≤ 300
  • grid[i][j] is "0" or "1"
In the interview

How to answer it out loud

What it tests: Graph traversal, visited-state choices, complexity analysis, and handling grid boundaries.

  1. 1
    Clarify

    Clarify adjacency rules, grid mutation, and whether the grid can be empty or ragged.

  2. 2
    Implement

    Scan every cell and launch DFS or BFS from each unvisited land cell, marking its entire component.

  3. 3
    Verify

    Test all water, all land, diagonal land, and narrow grids; state O(rows × columns) time.

Approaches

From brute force to the best solution

ApproachIdeaTimeSpace
Flood fill (BFS or DFS)BestScan every cell; each unvisited land cell starts a new island, and a fill marks its whole component.O(m·n)O(m·n) worst case
Union-findUnion each land cell with its land neighbours and count the distinct roots.O(m·n·α(m·n))O(m·n)
Key insight

Every land cell belongs to exactly one island. Counting how many times you start a fill from an unvisited land cell counts the islands. This version marks visited land as "0" in place — copy the grid first if the caller needs it unchanged.

Solution

Reference solution

Each version is self-contained and has been run against the examples and test cases on this page.

from collections import deque​​def num_islands(grid: list[list[str]]) -> int:    rows, cols = len(grid), len(grid[0])    islands = 0    for r in range(rows):        for c in range(cols):            if grid[r][c] != "1":                continue            islands += 1            grid[r][c] = "0"                 # mark when queued, not when popped            queue = deque([(r, c)])            while queue:                cr, cc = queue.popleft()                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"                        queue.append((nr, nc))    return islands
Time
O(m·n)
Space
O(m·n) worst case
Approach
Flood fill (BFS or DFS)
Test cases

Edge cases to run before you say “done”

InputExpectedWhy it matters
All water0No fill ever starts.
All land (300 × 300)1A recursive DFS can overflow the stack here; BFS cannot.
[["1","0","1"],["0","1","0"]]3Diagonals must not connect.
Likely follow-ups

Answer the main question first, then take these on one at a time:

  • Can you avoid a separate visited set?
  • When would BFS be safer than recursive DFS?
  • How would you process a grid too large for memory?
Avoid these mistakes

Check your recording or written solution against this list:

  • Counting diagonal cells as adjacent without agreement
  • Revisiting cells
  • Ignoring recursion-depth limits
Sources and methodology

This guide combines general interview-practice patterns with the public hiring material below. The practice prompt and coaching are PiriPiri AI editorial content, not official Amazon questions or answers.

Amazon: software development interview topics ↗Amazon: Leadership Principles ↗
Official sources reviewed 20 September 2026.