GitHub

Number of Islands medium

Description

Given an m × n grid of '1's (land) and '0's (water), return the number of islands. An island is a maximal group of '1's connected horizontally or vertically. The grid’s edges are surrounded by water (the grid does not wrap around).

Examples

> Case 1:
    Input:
        [['1','1','1','1','0'],
         ['1','1','0','1','0'],
         ['1','1','0','0','0'],
         ['0','0','0','0','0']]
    Output: 1      # all the 1s are connected
 
> Case 2:
    Input:
        [['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'

Intuition

This is the counting components pattern from Day 9, translated to a grid:

Sweep every cell in the grid.
When you find an unvisited land cell, increment the counter and flood-fill the entire island from there (DFS or BFS).
The flood-fill marks every cell of that island as visited so the sweep doesn’t double-count.

That’s it. Counting components is “count the number of times you kick off a new traversal.”

Approach 1: DFS flood-fill (mutating the grid)

The cleanest trick: instead of using a separate visited set, overwrite each visited '1' with '0'. We’re not using the grid for anything else once we’ve found an island.

⚠️

Mutating the input is fast and elegant — but it changes the caller’s grid. In an interview, mention it: “I’ll mark visited cells by setting them to ‘0’; if the grid shouldn’t be modified, I’ll use a separate visited set instead.” Adding visited doubles the memory, doesn’t affect time.

Approach 2: Iterative BFS (avoid recursion depth)

For very large grids, Python’s recursion limit becomes a problem. BFS sidesteps that:

Why this is the archetypal grid-DFS problem

Every grid DFS/BFS problem you’ll see is a variation:

Max Area of Island — return island sizes instead of count
Surrounded Regions — flip 'O' cells unless they touch the border
Pacific Atlantic — multi-source DFS from each border
Flood Fill — recolor connected region
Number of Distinct Islands — count up to translation

Master the Number of Islands template and these are all 5-minute edits.

Analysis

Time: O(m · n) — every cell visited at most once.
Space: O(m · n) worst case for the recursion stack / BFS queue when the entire grid is one big island.

Overview Max Area of Island