☕ DSA Java Articles

Topics › Graphs › Problems on BFS/DFS

Number of islands

Medium TUF ID 534 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

At this point of Striver’s A2Z graph section, right after Word Ladder II, the island problem is Number of Distinct Islands. The plain island count appears earlier in the sheet as Connected Components Problem in Matrix. This article covers the plain count briefly as a warm-up, because the distinct version is built directly on top of it.

You are given an n × m grid of 0s (water) and 1s (land). An island is a maximal group of land cells connected up, down, left or right. Two islands are considered the same if one can be shifted (translated) to coincide exactly with the other. Rotations and reflections do not count as the same. Return the number of distinct islands.

Constraints: 1 ≤ n, m ≤ 500.

Example 1

1 1 0 0 0
1 1 0 0 0
0 0 0 1 1
0 0 0 1 1
islands = 2, distinct = 1     // two 2x2 squares; shifting one gives the other

Example 2

1 1 0 1 1
1 0 0 0 0
0 0 0 0 1
1 1 0 1 1
islands = 4, distinct = 3

The two horizontal dominoes (top right and bottom left) have the same shape. The three-cell corners at the top left and bottom right are mirror images of each other, and mirroring is not allowed, so they count separately.

Warm-up: counting islands

Intuition. Scan the grid. Whenever we meet a land cell that no earlier flood has visited, it must belong to a new island, so we count it and flood the whole island with DFS, marking every cell. Each island is then counted exactly once, at its first cell in row-major order.

The flood below also records each cell’s position relative to the island’s first cell (r0, c0). The plain count ignores that list; the distinct count depends on it.

static int countIslands(int[][] grid) {
    boolean[][] vis = new boolean[grid.length][grid[0].length];
    int islands = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 1 && !vis[i][j]) {
                islands++;
                collect(grid, i, j, i, j, vis, new ArrayList<>());
            }
        }
    }
    return islands;
}

static void collect(int[][] grid, int r, int c, int r0, int c0, boolean[][] vis, List<int[]> cells) {
    if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length) return;
    if (grid[r][c] == 0 || vis[r][c]) return;
    vis[r][c] = true;
    cells.add(new int[]{r - r0, c - c0});
    for (int k = 0; k < 4; k++) collect(grid, r + DR[k], c + DC[k], r0, c0, vis, cells);
}

static final int[] DR = {-1, 0, 1, 0}, DC = {0, 1, 0, -1};

Complexity. Time O(n·m): every cell is visited once. Space O(n·m) for vis and the recursion.

Approach 1: Brute force, compare shapes one by one

Intuition. To decide whether two islands are translations of each other, remove their position. Subtract the coordinates of a reference cell from every cell; if the two resulting sets of offsets are equal, one island is the other shifted. The reference must be chosen the same way for both islands, and “the first cell met in the row-major scan” works: it is the top-most cell of the island, and among those the left-most, which is a property of the shape alone.

Then keep a list of the distinct shapes found so far and compare each new island with every one of them. Sorting the offsets puts both lists in the same order, so a simple element-by-element comparison decides equality.

Algorithm.

  1. Scan the grid; for each unvisited land cell, collect its island’s offsets with the flood above.
  2. Sort the offsets.
  3. Compare with every stored shape; if none matches, store it.
  4. Return the number of stored shapes.
static int bruteForce(int[][] grid) {
    boolean[][] vis = new boolean[grid.length][grid[0].length];
    List<List<int[]>> shapes = new ArrayList<>();
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] != 1 || vis[i][j]) continue;
            List<int[]> cells = new ArrayList<>();
            collect(grid, i, j, i, j, vis, cells);
            cells.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
            boolean seen = false;
            for (List<int[]> s : shapes) {
                if (sameShape(s, cells)) { seen = true; break; }
            }
            if (!seen) shapes.add(cells);
        }
    }
    return shapes.size();
}

static boolean sameShape(List<int[]> a, List<int[]> b) {
    if (a.size() != b.size()) return false;
    for (int k = 0; k < a.size(); k++) {
        if (a.get(k)[0] != b.get(k)[0] || a.get(k)[1] != b.get(k)[1]) return false;
    }
    return true;
}

Complexity. Time O(n·m · D) in the worst case, where D is the number of distinct shapes, because each island is compared against up to D stored shapes. Many tiny islands with different shapes push this towards O((n·m)^2). Space O(n·m) for the stored shapes.

Approach 2: Optimal, hash the shape

Intuition. The linear search through stored shapes is what makes the brute force slow, and a hash set removes it. We only need a canonical key for each shape: a value that is equal for two islands exactly when they are translations of each other. Then the answer is simply the size of a HashSet of keys.

The offsets in DFS visit order already form such a key, even without sorting. Two islands with the same shape are explored identically: the DFS starts at the same relative cell, tries directions in the same fixed order, and at every step the question “is this neighbour unvisited land?” has the same answer for both, because a cell next to an island is either part of that island or water. So both DFS runs produce the same sequence of offsets. Two islands with different shapes have different sets of offsets, so their keys differ too.

The key is a string like "0,0;0,1;1,0;". The separators matter: without them the offsets (1, 12) and (11, 2) would both read "112".

Algorithm.

  1. Scan the grid; for each unvisited land cell, collect its island’s offsets in DFS order.
  2. Turn the offsets into a string key and add it to a set.
  3. Return the size of the set.
static int optimal(int[][] grid) {
    boolean[][] vis = new boolean[grid.length][grid[0].length];
    Set<String> shapes = new HashSet<>();
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] != 1 || vis[i][j]) continue;
            List<int[]> cells = new ArrayList<>();
            collect(grid, i, j, i, j, vis, cells);
            StringBuilder key = new StringBuilder();
            for (int[] cell : cells) key.append(cell[0]).append(',').append(cell[1]).append(';');
            shapes.add(key.toString());
        }
    }
    return shapes.size();
}

Dry run on Example 2, scanning row by row:

island found at offsets in DFS order key new?
(0,0) (0,0) (0,1) (1,0) yes
(0,3) (0,0) (0,1) yes
(2,4) (0,0) (1,0) (1,-1) yes
(3,0) (0,0) (0,1) no, same as the island at (0,3)

The set holds three keys, so the answer is 3. The corner at (2,4) produces a negative column offset, which is why the key keeps signs and separators.

Complexity. Time O(n·m): each cell is visited once and contributes a constant-length piece to one key, and hashing a key costs its length. Space O(n·m) for the keys, vis, and recursion.

Edge cases and pitfalls