200. Number of Islands (Medium)

Problem

Given an m × n grid of "1" (land) and "0" (water), return the number of islands. An island is formed by connecting adjacent land cells horizontally or vertically.

Example

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

LeetCode 200 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: DFS with in-place mutation

Scan the grid; for each land cell, DFS to mark every connected land cell as water (visited). Each DFS trigger = one island.

Python

def num_islands(grid):
    if not grid:                                                        # L1: guard empty input
        return 0
    rows, cols = len(grid), len(grid[0])                               # L2: O(1)
    count = 0                                                          # L3: O(1)

    def dfs(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != "1":  # L4: O(1) boundary check
            return
        grid[r][c] = "0"                                               # L5: O(1) mark visited
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)   # L6: recurse 4 neighbors

    for r in range(rows):                                              # L7: outer scan loop
        for c in range(cols):                                          # L8: inner scan loop
            if grid[r][c] == "1":
                count += 1
                dfs(r, c)                                              # L9: DFS from new island root
    return count

TypeScript

function numIslands(grid: string[][]): number {
    if (grid.length === 0) return 0;                                   // L1: guard empty input
    const rows = grid.length, cols = grid[0].length;                   // L2: O(1)
    let count = 0;                                                     // L3: O(1)

    function dfs(r: number, c: number): void {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') return;  // L4: boundary
        grid[r][c] = '0';                                              // L5: O(1) mark visited
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1); // L6: recurse 4 neighbors
    }

    for (let r = 0; r < rows; r++) {                                   // L7: outer scan loop
        for (let c = 0; c < cols; c++) {                               // L8: inner scan loop
            if (grid[r][c] === '1') {
                count++;
                dfs(r, c);                                             // L9: DFS from new island root
            }
        }
    }
    return count;
}

Go

func numIslands(grid [][]byte) int {
    if len(grid) == 0 {                                                // L1: guard empty input
        return 0
    }
    rows, cols := len(grid), len(grid[0])                             // L2: O(1)
    count := 0                                                        // L3: O(1)

    var dfs func(r, c int)
    dfs = func(r, c int) {
        if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1' { // L4: boundary check
            return
        }
        grid[r][c] = '0'                                              // L5: O(1) mark visited
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)          // L6: recurse 4 neighbors
    }

    for r := 0; r < rows; r++ {                                       // L7: outer scan loop
        for c := 0; c < cols; c++ {                                   // L8: inner scan loop
            if grid[r][c] == '1' {
                count++
                dfs(r, c)                                             // L9: DFS from new island root
            }
        }
    }
    return count
}

Swift

final class Solution {
    func numIslands(_ grid: [[Character]]) -> Int {
        var grid = grid
        let rows = grid.count, cols = grid[0].count
        func sink(_ row: Int, _ col: Int) {
            if row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] != "1" { return }
            grid[row][col] = "0"
            sink(row + 1, col); sink(row - 1, col); sink(row, col + 1); sink(row, col - 1)
        }
        var islands = 0
        for row in 0..<rows {
            for col in 0..<cols where grid[row][col] == "1" { islands += 1; sink(row, col) }
        }
        return islands
    }
}

Where the time goes, line by line

Variables: m = grid rows, n = grid cols.

Line	Per-call cost	Times executed	Contribution
L7, L8 (scan)	$O(1)$	m · n	$O(m · n)$
L4 (boundary check)	$O(1)$	once per cell entered via DFS	$O(m · n)$ total
L5 (mark visited)	$O(1)$	at most once per land cell	$O(m · n)$ total
L6 (recurse)	$O(1)$ per call	each cell visited at most once	$O(m · n)$ ← dominates

Every land cell is flipped from "1" to "0" exactly once, so L6 fires at most m · n times total across the entire outer loop, not per island. The recursion stack depth is at most m · n in a pathological all-land grid.

Complexity

• Time: $O(m · n)$, driven by L6/L9 (each cell visited at most once in total).
• Space: $O(m · n)$ recursion worst case.

Approach 2: BFS with a queue

Same idea, BFS instead of DFS, avoids deep recursion on large grids.

Python

from collections import deque

def num_islands(grid):
    if not grid:                                                      # L1: guard empty input
        return 0
    rows, cols = len(grid), len(grid[0])                             # L2: O(1)
    count = 0                                                        # L3: O(1)

    def bfs(r, c):
        q = deque([(r, c)])                                          # L4: O(1) seed queue
        grid[r][c] = "0"                                             # L5: O(1) mark root visited
        while q:                                                     # L6: process until queue empty
            x, y = q.popleft()                                       # L7: O(1) dequeue
            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == "1":
                    grid[nx][ny] = "0"                               # L8: O(1) mark visited
                    q.append((nx, ny))                               # L9: O(1) enqueue neighbor

    for r in range(rows):                                            # L10: outer scan
        for c in range(cols):                                        # L11: inner scan
            if grid[r][c] == "1":
                count += 1
                bfs(r, c)                                            # L12: BFS from new island root
    return count

TypeScript

function numIslands(grid: string[][]): number {
    if (grid.length === 0) return 0;                                  // L1: guard empty input
    const rows = grid.length, cols = grid[0].length;                  // L2: O(1)
    let count = 0;                                                    // L3: O(1)

    function bfs(r: number, c: number): void {
        const q: [number, number][] = [[r, c]];                       // L4: O(1) seed queue
        grid[r][c] = '0';                                             // L5: O(1) mark root visited
        let head = 0;
        while (head < q.length) {                                     // L6: process until queue empty
            const [x, y] = q[head++];                                 // L7: O(1) dequeue
            for (const [dx, dy] of [[1,0],[-1,0],[0,1],[0,-1]]) {
                const nx = x + dx, ny = y + dy;
                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] === '1') {
                    grid[nx][ny] = '0';                               // L8: O(1) mark visited
                    q.push([nx, ny]);                                 // L9: O(1) enqueue neighbor
                }
            }
        }
    }

    for (let r = 0; r < rows; r++) {                                  // L10: outer scan
        for (let c = 0; c < cols; c++) {                              // L11: inner scan
            if (grid[r][c] === '1') {
                count++;
                bfs(r, c);                                            // L12: BFS from new island root
            }
        }
    }
    return count;
}

Go

func numIslands(grid [][]byte) int {
    if len(grid) == 0 {                                               // L1: guard empty input
        return 0
    }
    rows, cols := len(grid), len(grid[0])                            // L2: O(1)
    count := 0                                                       // L3: O(1)
    dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

    bfs := func(r, c int) {
        queue := [][2]int{{r, c}}                                    // L4: O(1) seed queue
        grid[r][c] = '0'                                             // L5: O(1) mark root visited
        for len(queue) > 0 {                                         // L6: process until queue empty
            cur := queue[0]; queue = queue[1:]                       // L7: O(1) dequeue
            for _, d := range dirs {
                nr, nc := cur[0]+d[0], cur[1]+d[1]
                if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1' {
                    grid[nr][nc] = '0'                               // L8: O(1) mark visited
                    queue = append(queue, [2]int{nr, nc})            // L9: O(1) enqueue neighbor
                }
            }
        }
    }

    for r := 0; r < rows; r++ {                                      // L10: outer scan
        for c := 0; c < cols; c++ {                                  // L11: inner scan
            if grid[r][c] == '1' {
                count++
                bfs(r, c)                                            // L12: BFS from new island root
            }
        }
    }
    return count
}

Swift

final class Solution {
    func numIslands(_ grid: [[Character]]) -> Int {
        let rows = grid.count, cols = grid[0].count
        var seen = Set<Int>(), islands = 0
        for row in 0..<rows {
            for col in 0..<cols where grid[row][col] == "1" && !seen.contains(row * cols + col) {
                islands += 1
                var queue = [(row, col)], head = 0
                seen.insert(row * cols + col)
                while head < queue.count {
                    let (r, c) = queue[head]; head += 1
                    for (dr, dc) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
                        let nr = r + dr, nc = c + dc, key = nr * cols + nc
                        if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == "1" && seen.insert(key).inserted {
                            queue.append((nr, nc))
                        }
                    }
                }
            }
        }
        return islands
    }
}

Where the time goes, line by line

Variables: m = grid rows, n = grid cols.

Line	Per-call cost	Times executed	Contribution
L10, L11 (scan)	$O(1)$	m · n	$O(m · n)$
L7 (dequeue)	$O(1)$	at most once per land cell	$O(m · n)$ total
L8 (mark visited)	$O(1)$	at most once per land cell	$O(m · n)$ total
L9 (enqueue)	$O(1)$	each land cell enqueued at most once	$O(m · n)$ ← dominates

The queue holds at most min(m, n) cells at any instant (the BFS frontier cannot exceed the shorter grid dimension), but total enqueue operations across the whole run are bounded by m · n.

Complexity

• Time: $O(m · n)$, driven by L9/L12 (each cell enqueued at most once in total).
• Space: $O(min(m, n)$) queue (max frontier width).

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space	Notes
DFS	$O(m · n)$	$O(m · n)$ recursion	Canonical
BFS	$O(m · n)$	$O(min(m, n)$)	Use when grids are deep (avoid recursion depth)
Union-Find	$O(m · n · α)$	$O(m · n)$	Overkill here, template for incremental updates

DFS/BFS are equivalent in Big-O. Choose Union-Find when the graph is growing over time, adding edges online and asking “how many components now?”

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_200.py and run.
# Uses the canonical implementation (Approach 1: DFS).

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != "1":
            return
        grid[r][c] = "0"
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                dfs(r, c)
    return count

def _run_tests():
    # Example 1: single island
    g1 = [["1","1","1","1","0"],
          ["1","1","0","1","0"],
          ["1","1","0","0","0"],
          ["0","0","0","0","0"]]
    assert num_islands(g1) == 1

    # Example 2: three islands
    g2 = [["1","1","0","0","0"],
          ["1","1","0","0","0"],
          ["0","0","1","0","0"],
          ["0","0","0","1","1"]]
    assert num_islands(g2) == 3

    # Edge: empty grid
    assert num_islands([]) == 0

    # Edge: single land cell
    assert num_islands([["1"]]) == 1

    # Edge: single water cell
    assert num_islands([["0"]]) == 0

    # All land, one island
    g3 = [["1","1"],["1","1"]]
    assert num_islands(g3) == 1

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function numIslands(grid: string[][]): number {
    if (grid.length === 0) return 0;
    const rows = grid.length, cols = grid[0].length;
    let count = 0;

    function dfs(r: number, c: number): void {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') return;
        grid[r][c] = '0';
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
    }

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1') { count++; dfs(r, c); }
        }
    }
    return count;
}

const g1 = [['1','1','1','1','0'],['1','1','0','1','0'],['1','1','0','0','0'],['0','0','0','0','0']];
console.assert(numIslands(g1) === 1);
const g2 = [['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']];
console.assert(numIslands(g2) === 3);
console.assert(numIslands([]) === 0);
console.assert(numIslands([['1']]) === 1);
console.assert(numIslands([['0']]) === 0);
console.assert(numIslands([['1','1'],['1','1']]) === 1);
console.log("all tests pass");

Related data structures

• Arrays, the grid; in-place mutation as visited marker
• Queues, BFS
• Stacks, implicit via DFS recursion

Related concepts

• DFS, depth-first traversal tactics for exploring one branch fully before backtracking to alternatives.
• Flood Fill, grid traversal tactics for expanding through adjacent cells that share a condition.
• Graph Traversal, visited-state tactics for exploring nodes, edges, components, and reachability relationships.