Number of Islands

MEDIUM✓ CHIP-TIMEDLC #200 — FULL STATEMENT ↗

The drill: A grid of '1' (land) and '0' (water) cells — count how many separate islands exist, where land only connects up, down, left, or right, never diagonally.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A grid of characters, each either '1' for land or '0' for water, represents a small stretch of coastline. The task is to count how many separate islands sit in that grid, where an island is any group of land cells joined edge to edge.

Two land cells only belong to the same island when connected up, down, left, or right — a diagonal touch never merges two islands into one, no matter how close the corners sit.

The grid is scanned as a whole; nothing needs sorting or ranking, just a count of distinct connected land groups by the time every cell has been looked at.

EX 01

grid = ["1"]

→ 1

SINGLE LAND CELL

EX 02

grid = ["0"]

→ 0

SINGLE WATER CELL

EX 03

grid = ["101"]

→ 2

TWO ISLANDS SEPARATED BY WATER

grid holds up to a few hundred rows and columns
cells are the characters '1' or '0', nothing else
connectivity is 4-directional — diagonals never join two islands
an all-water grid is a valid input worth zero islands

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Every land cell belongs to exactly one island; the question is how many separate blobs of connected land exist. What operation turns 'walk through everything connected to me' into a single check?

HINT 2 THE STRUCTURE

Flood fill: starting from any unvisited land cell, mark every cell reachable through land moves as belonging to the same island, then never look at those cells again.

HINT 3 ONE STEP FROM THE ANSWER

Scan every cell; each time you hit unvisited land, that's a brand-new island — flood-fill outward from it (BFS or DFS) to consume the whole blob before continuing the scan.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE SINK COUNTPATTERN · DFS, SINK IN PLACEgrid = ["110","010","001"]

STEP 1

Scan every cell left to right, top to bottom. Each unvisited '1' starts a brand-new island, then DFS sinks its whole blob to '0'.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/number-of-islands.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows, cols = len(grid), len(grid[0])

        def sink(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
                return
            grid[r][c] = '0'
            sink(r + 1, c)
            sink(r - 1, c)
            sink(r, c + 1)
            sink(r, c - 1)

        islands = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    islands += 1
                    sink(r, c)
        return islands

TIME O(ROWS·COLS)SPACE O(ROWS·COLS) WORST CASE (CALL STACK)PYTHON · RACE PACE · 20 LN

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows, cols = len(grid), len(grid[0])
        visited = [[False] * cols for _ in range(rows)]
        islands = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1' and not visited[r][c]:
                    islands += 1
                    queue = collections.deque([(r, c)])
                    visited[r][c] = True
                    while queue:
                        cr, cc = queue.popleft()
                        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                            nr, nc = cr + dr, cc + dc
                            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1' and not visited[nr][nc]:
                                visited[nr][nc] = True
                                queue.append((nr, nc))
        return islands

TIME O(ROWS·COLS)SPACE O(ROWS·COLS)PYTHON · TRAINING PACE · 19 LN

class Solution {
    public int numIslands(char[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int islands = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    islands++;
                    sink(grid, r, c);
                }
            }
        }
        return islands;
    }

    private void sink(char[][] grid, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1') return;
        grid[r][c] = '0';
        sink(grid, r + 1, c);
        sink(grid, r - 1, c);
        sink(grid, r, c + 1);
        sink(grid, r, c - 1);
    }
}

TIME O(ROWS·COLS)SPACE O(ROWS·COLS) WORST CASE (CALL STACK)JAVA · RACE PACE · 24 LN

class Solution {
    public int numIslands(char[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        int islands = 0;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1' && !visited[r][c]) {
                    islands++;
                    Deque<int[]> queue = new ArrayDeque<>();
                    queue.add(new int[]{r, c});
                    visited[r][c] = true;
                    while (!queue.isEmpty()) {
                        int[] cell = queue.poll();
                        for (int[] d : dirs) {
                            int nr = cell[0] + d[0], nc = cell[1] + d[1];
                            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1' && !visited[nr][nc]) {
                                visited[nr][nc] = true;
                                queue.add(new int[]{nr, nc});
                            }
                        }
                    }
                }
            }
        }
        return islands;
    }
}

TIME O(ROWS·COLS)SPACE O(ROWS·COLS)JAVA · TRAINING PACE · 29 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED