Skip to content
LEETFLIX

Number of Islands

MediumArrayDFSBFSUnion-findMatrix
Solve on LeetCode

Flood fill, the interview edition. Count components in a grid by sinking them as you go.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

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.

Constraints

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

Examples

Input

grid =
["11110", "11010", "11000", "00000"]

Output

1

grid

1
1
1
1
0
1
1
0
1
0
1
1
0
0
0
0
0
0
0
0

All the 1s are connected through shared edges — one island.

02

Solution

2 approaches · Python and Go. Pick a tab — the walkthrough follows.

Optimal▶ Animated

Scan every cell; on land, count one island and recursively sink everything connected to it.

sink(r, c) turns a land cell to water and recurses into its four neighbours. Out-of-bounds or water cells return immediately. After the call, that entire island is gone from the grid and can't be counted twice.

Algorithm

  1. count = 0.
  2. For every cell (r, c): if it's '1', count += 1 and call sink(r, c).
  3. sink: return if out of bounds or not land; set to '0'; recurse to 4 neighbours.
  4. Return count.
Time
O(m · n)
Space
O(m · n)

Every cell is visited a constant number of times. Space is recursion depth in the worst case.

Solution.py
class Solution:    def numIslands(self, grid: list[list[str]]) -> int:        rows, cols = len(grid), len(grid[0])        count = 0         def sink(r: int, c: int) -> None:            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":                return            grid[r][c] = "0"  # mark visited by sinking the land            sink(r + 1, c)            sink(r - 1, c)            sink(r, c + 1)            sink(r, c - 1)         for r in range(rows):            for c in range(cols):                if grid[r][c] == "1":                    count += 1   # new, never-seen island                    sink(r, c)   # remove all of it        return count
Watch this run

03

Interactive walkthrough

Playing “DFS with sinking”. Edit the input, hit Run, then scrub.

Approach: DFS with sinking

Loading animation…