20  Number of Islands

Rank 18 · Pattern: count connected components with grid DFS · Target: \(O(rows\times columns)\) time

20.1 Problem definition

Given a two-dimensional grid of land and water cells, return the number of separate islands in the grid. An island is a connected region of land.

20.2 Clarifying questions

  1. How are land and water represented?
  2. Which neighboring cells are considered connected? Do diagonals count?
  3. Can the grid be empty, and is it guaranteed to be rectangular?
  4. May I modify the input grid?
  5. Can the grid or any row be null?

20.3 Sample answers

  1. Land is '1' and water is '0'.
  2. Only horizontal and vertical neighbors connect; diagonal contact does not.
  3. The grid may have no rows or zero columns. When rows exist, they all have the same length.
  4. Yes. Changing cells in the input is allowed.
  5. No. The grid and all of its rows are non-null.

20.4 Data structure: mutable grid

No separate visited set is necessary because the contract permits changing visited land from '1' to '0'.

char[][] is an array of row arrays; access a cell as grid[row][col].

The grid is a list of mutable character lists. A string row is converted with list(row) in test fixtures because strings themselves are immutable.

The function borrows &mut [Vec<char>], making mutation explicit without taking ownership of the grid. Signed temporary coordinates make the up/left boundary checks direct.

The helper makes four direct recursive calls, one for each allowed direction:

visitIsland(grid, row + 1, col);
visitIsland(grid, row - 1, col);
visitIsland(grid, row, col + 1);
visitIsland(grid, row, col - 1);
1 1 0 0 0      A A . . .
1 1 0 0 0  ->  A A . . .
0 0 1 0 0      . . B . .
0 0 0 1 1      . . . C C     three components

20.5 Approach and invariant

Scan every cell. When unvisited land is found, increment the island count and call visitIsland, which changes that cell and all connected land to '0'. Each recursive call immediately returns for an out-of-bounds coordinate or a non-land cell.

Invariant: every cell changed to '0' by a visitIsland call belongs to the island that started that traversal, and no remaining '1' has been assigned to an earlier island.

%%{init: {
  "theme": "base",
  "flowchart": {
    "htmlLabels": false
  },
  "themeVariables": {
    "primaryColor": "#ffffff",
    "secondaryColor": "#ffffff",
    "tertiaryColor": "#ffffff",
    "primaryTextColor": "#222222",
    "primaryBorderColor": "#555555",
    "lineColor": "#555555",
    "edgeLabelBackground": "#ffffff"
  }
}}%%
flowchart TB
  A["Scan the next grid cell"]
  B{"Is it unvisited land?"}
  C["NO: continue the grid scan"]
  D["YES: increment islands and call visitIsland"]
  E{"Is this call outside the grid or not on land?"}
  F["YES: return from this call"]
  G["NO: mark the cell as water"]
  H["Visit its four horizontal and vertical neighbors"]
  I["After the traversal returns, resume the grid scan"]

  A --> B
  B --> C
  C --> A
  B --> D
  D --> E
  E --> F
  E --> G
  G --> H
  H --> E
  H --> I
  I --> A

  classDef plain fill:#ffffff,stroke:#555555,stroke-width:1.5px,color:#222222;
  class A,B,C,D,E,F,G,H,I plain;

20.6 Minimal solution

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class NumberOfIslandsSolution {
    static int numberOfIslands(char[][] grid) {
        int islands = 0;
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[row].length; col++) {
                if (grid[row][col] == '1') {
                    islands++;
                    visitIsland(grid, row, col);
                }
            }
        }
        return islands;
    }

    static void visitIsland(char[][] grid, int row, int col) {
        if (row < 0 || row >= grid.length
                || col < 0 || col >= grid[row].length
                || grid[row][col] != '1') {
            return;
        }

        grid[row][col] = '0';
        visitIsland(grid, row + 1, col);
        visitIsland(grid, row - 1, col);
        visitIsland(grid, row, col + 1);
        visitIsland(grid, row, col - 1);
    }

    @Test public void gridWithNoRowsHasNoIslands() {
        assertEquals(0, numberOfIslands(new char[0][0]));
    }

    @Test public void gridWithZeroColumnsHasNoIslands() {
        assertEquals(0, numberOfIslands(new char[][] {{}}));
    }

    @Test public void allWaterHasNoIslands() {
        assertEquals(0, numberOfIslands(new char[][] {{'0', '0'}}));
    }

    @Test public void singleLandCellIsOneIsland() {
        assertEquals(1, numberOfIslands(new char[][] {{'1'}}));
    }

    @Test public void diagonalCellsAreSeparate() {
        assertEquals(2, numberOfIslands(new char[][] {{'1','0'}, {'0','1'}}));
    }

    @Test public void countsOneLargeIsland() {
        assertEquals(1, numberOfIslands(new char[][] {
            {'1', '1', '1'},
            {'1', '1', '1'}
        }));
    }

    @Test public void handlesOneColumn() {
        assertEquals(2, numberOfIslands(new char[][] {{'1'}, {'0'}, {'1'}}));
    }

    @Test public void countsSeparateComponents() {
        char[][] grid = {{'1','1','0','0','0'}, {'1','1','0','0','0'},
                         {'0','0','1','0','0'}, {'0','0','0','1','1'}};
        assertEquals(3, numberOfIslands(grid));
    }

    public static void main(String[] args) {
        JUnitCore.main("NumberOfIslandsSolution");
    }
}
import unittest


def number_of_islands(grid):
    def visit_island(row, column):
        if (
            row < 0
            or row >= len(grid)
            or column < 0
            or column >= len(grid[row])
            or grid[row][column] != "1"
        ):
            return

        grid[row][column] = "0"
        visit_island(row + 1, column)
        visit_island(row - 1, column)
        visit_island(row, column + 1)
        visit_island(row, column - 1)

    islands = 0
    for row in range(len(grid)):
        for column in range(len(grid[row])):
            if grid[row][column] == "1":
                islands += 1
                visit_island(row, column)

    return islands


def make_grid(*rows):
    return [list(row) for row in rows]


class NumberOfIslandsTests(unittest.TestCase):
    def test_empty_grid(self):
        self.assertEqual(0, number_of_islands([]))

    def test_all_water(self):
        self.assertEqual(0, number_of_islands(make_grid("00")))

    def test_single_land_cell(self):
        self.assertEqual(1, number_of_islands(make_grid("1")))

    def test_diagonal_cells_are_separate(self):
        self.assertEqual(2, number_of_islands(make_grid("10", "01")))

    def test_counts_one_large_island(self):
        self.assertEqual(1, number_of_islands(make_grid("111", "111")))

    def test_counts_separate_components(self):
        grid = make_grid("11000", "11000", "00100", "00011")
        self.assertEqual(3, number_of_islands(grid))

    def test_marks_visited_land_as_water(self):
        grid = make_grid("11")
        number_of_islands(grid)
        self.assertEqual(make_grid("00"), grid)


if __name__ == "__main__":
    unittest.main()
pub fn number_of_islands(grid: &mut [Vec<char>]) -> usize {
    fn visit_island(grid: &mut [Vec<char>], row: isize, column: isize) {
        if row < 0 || row as usize >= grid.len() {
            return;
        }
        let row_index = row as usize;
        if column < 0
            || column as usize >= grid[row_index].len()
            || grid[row_index][column as usize] != '1'
        {
            return;
        }

        grid[row_index][column as usize] = '0';
        visit_island(grid, row + 1, column);
        visit_island(grid, row - 1, column);
        visit_island(grid, row, column + 1);
        visit_island(grid, row, column - 1);
    }

    let mut islands = 0;
    for row in 0..grid.len() {
        for column in 0..grid[row].len() {
            if grid[row][column] == '1' {
                islands += 1;
                visit_island(grid, row as isize, column as isize);
            }
        }
    }
    islands
}

#[cfg(test)]
mod tests {
    use super::*;

    fn grid(rows: &[&str]) -> Vec<Vec<char>> {
        rows.iter().map(|row| row.chars().collect()).collect()
    }

    #[test]
    fn empty_grid() {
        assert_eq!(0, number_of_islands(&mut []));
    }

    #[test]
    fn all_water() {
        assert_eq!(0, number_of_islands(&mut grid(&["00"])));
    }

    #[test]
    fn single_land_cell() {
        assert_eq!(1, number_of_islands(&mut grid(&["1"])));
    }

    #[test]
    fn diagonal_cells_are_separate() {
        assert_eq!(2, number_of_islands(&mut grid(&["10", "01"])));
    }

    #[test]
    fn counts_one_large_island() {
        assert_eq!(1, number_of_islands(&mut grid(&["111", "111"])));
    }

    #[test]
    fn counts_separate_components() {
        let mut input = grid(&["11000", "11000", "00100", "00011"]);
        assert_eq!(3, number_of_islands(&mut input));
    }

    #[test]
    fn marks_visited_land_as_water() {
        let mut input = grid(&["11"]);
        number_of_islands(&mut input);
        assert_eq!(grid(&["00"]), input);
    }
}

20.7 High-value tests

Grid Expected Purpose
empty 0 boundary
all water 0 no traversal
all land 1 one large component
diagonal ones 2 no diagonal adjacency
sample with three regions 3 multiple components
one row / one column varies boundary neighbors

20.8 Complexity and correctness

Every cell is scanned, and each land cell is visited once, so time is \(O(rc)\). The recursion stack can reach \(O(rc)\) for one long connected island. Mutation supplies the visited marking without another \(O(rc)\) structure.

Each traversal reaches exactly the four-direction component of its starting cell. Marking removes that whole component from future consideration. Therefore every increment corresponds to one distinct island, and the full scan eventually starts a traversal for every component.

20.9 If the interviewer pushes

  • Preserve the input with a boolean[][] visited, using \(O(rc)\) extra space.
  • Use an explicit queue for breadth-first search if the grid can contain an island large enough to overflow the call stack.
  • Return island areas by counting visited land cells; return the maximum by tracking the largest count.
  • For a stream of rows or dynamic land additions, different techniques such as union-find may be appropriate.

20.10 TDD interview script

Confirm '1' is land, '0' is water, only four-direction neighbors connect, the grid is non-null and rectangular but may have zero rows or columns, and mutation is allowed. Then write this test list:

  1. No rows
  2. Zero columns
  3. All water
  4. One land cell
  5. One connected region
  6. Diagonal separation
  7. One-column boundary case
  8. Several components

Add one focused test per red–green–refactor cycle. Make the topology visible in each fixture, verify red, add the next scan or traversal rule, and rerun the complete example. Test the island count rather than recursive call order; input mutation is an allowed technique, not a required output behavior.

From book/src, run:

./java/run.sh NumberOfIslandsSolution
./python/run.sh number_of_islands_solution
./rust/run.sh number_of_islands_solution

Explain the count/traverse division: increment exactly when the outer scan finds unvisited land, then erase that entire four-direction component so no later cell can count it again.

20.10.1 Pseudocode

islands = 0
for every row and column:
    if cell is land:
        islands++
        visitIsland(row, column)
return islands

visitIsland(row, column):
    if outside grid or cell is not land:
        return
    mark cell as water
    visit down, up, right, and left neighbors

Every cell erased by one traversal belongs to its starting island, and no remaining land cell has already been assigned to a previously counted island.

20.10.2 TDD sequence

Step Test code added Production code added or changed
1. No rows gridWithNoRowsHasNoIslands Introduce the nested scan and return the initial zero count when no rows exist.
2. No columns gridWithZeroColumnsHasNoIslands Use each row’s length as the inner bound so a zero-width grid scans safely.
3. Water only allWaterHasNoIslands Increment only when the scanned cell is '1'.
4. First island singleLandCellIsOneIsland Increment for land and mark it visited before exploring neighbors.
5. Connected component countsOneLargeIsland Recursively visit four neighbors and stop on water or out-of-bounds coordinates.
6. No diagonals diagonalCellsAreSeparate Keep traversal to exactly up, down, left, and right; diagonal land starts another island.
7. Boundary traversal handlesOneColumn Exercise vertical movement and both column boundaries across multiple components.
8. Complete scan countsSeparateComponents Alternate full-component erasure with continued scanning to count several differently shaped islands.

The progression separates grid-shape boundaries from connectivity. Mark-before-recursing is the key safety rule: it prevents cycles between neighboring land cells and makes every land cell linear-time work.