☕ DSA Java Articles

Topics › Graphs › MinimumSpanningTree/Disjoint Set and Problems

Number of islands II

Hard TUF ID 514 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an n x m grid in which every cell starts as water, and a list of k operations. Operation i is a cell [row, col] that turns into land. After every operation, report the number of islands, where an island is a maximal group of land cells connected horizontally or vertically (not diagonally).

An operation may name a cell that is already land. Then nothing changes and the count is reported again.

Constraints (LeetCode version): 1 ≤ n, m ≤ 10^4, n · m ≤ 10^4, 1 ≤ k ≤ 10^4. Other versions allow larger grids; the approaches do not change.

Example 1

n = 4, m = 5, operators = [[1,1],[0,1],[3,3],[3,4]]
answer = [1, 1, 2, 2]
// (1,1) new island; (0,1) joins it; (3,3) new island; (3,4) joins (3,3)

Example 2

n = 3, m = 3, operators = [[0,1],[1,0],[1,2],[2,1],[1,1]]
answer = [1, 2, 3, 4, 1]
// four separate cells around the centre, then the centre joins all four

Example 2 shows why this problem is interesting: a single new cell can reduce the island count by three at once.

Approach 1: Brute force, recount after every operation

Intuition. We already know how to count islands in a static grid: scan every cell, and each time we find an unvisited land cell, flood its whole island with BFS and add one. Apply that after every operation. It is obviously correct, because each answer is computed from scratch on the current grid.

The waste is just as obvious: an operation changes one cell, yet we re-examine all n · m cells.

Algorithm.

  1. Keep a boolean grid land.
  2. For each operation, mark the cell as land and call countIslands.
  3. countIslands scans the grid; every unvisited land cell starts a BFS that marks its whole island, and increments the count.
static List<Integer> bruteForce(int n, int m, int[][] operators) {
    boolean[][] land = new boolean[n][m];
    List<Integer> answer = new ArrayList<>();
    for (int[] op : operators) {
        land[op[0]][op[1]] = true;
        answer.add(countIslands(land));
    }
    return answer;
}

static int countIslands(boolean[][] land) {
    int n = land.length, m = land[0].length, count = 0;
    boolean[][] seen = new boolean[n][m];
    Deque<int[]> queue = new ArrayDeque<>();
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (!land[r][c] || seen[r][c]) continue;
            count++;                                     // new island found, flood it
            seen[r][c] = true;
            queue.add(new int[]{r, c});
            while (!queue.isEmpty()) {
                int[] cell = queue.poll();
                for (int k = 0; k < 4; k++) {
                    int nr = cell[0] + DR[k], nc = cell[1] + DC[k];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < m && land[nr][nc] && !seen[nr][nc]) {
                        seen[nr][nc] = true;
                        queue.add(new int[]{nr, nc});
                    }
                }
            }
        }
    }
    return count;
}

Complexity. Time O(k · n · m): each of the k recounts visits every cell a constant number of times. Space O(n · m) for the grid, the seen array and the queue. With k = 10^4 and a 10^4-cell grid that is already 10^8 cell visits, and it grows with both inputs.

Approach 2: Disjoint Set, update the count incrementally

Intuition. Think about what one operation does to the island count:

Distinguishing “different island” from “same island” is exactly what a Disjoint Set answers. Number the cells r * m + c, start each one in its own set, and union the new cell with each land neighbour. union returns true only when it merged two different sets, so every true means one fewer island.

The sets of water cells are never touched, so they never affect the count. Only cells that have been switched to land participate in unions.

Why not simply store an island label in every cell and relabel on a merge? That works if you always relabel the smaller island (each cell then changes label at most log2(n · m) times), but it needs a member list per island and a single merge can still touch thousands of cells. The Disjoint Set gets the same effect with two arrays and does the relabelling lazily: a merge rewires one root pointer, and path compression fixes the other pointers the next time they are used.

static final class DisjointSet {
    final int[] parent, size;

    DisjointSet(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);   // path compression
        return parent[x];
    }

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;                         // already in the same set
        if (size[ra] < size[rb]) {
            int t = ra;
            ra = rb;
            rb = t;
        }
        parent[rb] = ra;                                    // hang the smaller tree under the larger
        size[ra] += size[rb];
        return true;
    }
}

Algorithm.

  1. Create a Disjoint Set over n · m cell ids, an all-water land grid, and islands = 0.
  2. For each operation (r, c):
    • If land[r][c] is already true, append islands unchanged and continue.
    • Mark it land and do islands++.
    • For each of the four neighbours that is inside the grid and is land, union it with (r, c); on success do islands--.
    • Append islands.
static List<Integer> disjointSet(int n, int m, int[][] operators) {
    DisjointSet ds = new DisjointSet(n * m);
    boolean[][] land = new boolean[n][m];
    List<Integer> answer = new ArrayList<>();
    int islands = 0;
    for (int[] op : operators) {
        int r = op[0], c = op[1];
        if (land[r][c]) {                                   // repeated operation: nothing changes
            answer.add(islands);
            continue;
        }
        land[r][c] = true;
        islands++;
        for (int k = 0; k < 4; k++) {
            int nr = r + DR[k], nc = c + DC[k];
            if (nr >= 0 && nr < n && nc >= 0 && nc < m && land[nr][nc]) {
                if (ds.union(r * m + c, nr * m + nc)) islands--;
            }
        }
        answer.add(islands);
    }
    return answer;
}

Dry run on example 2 (3 x 3, cell id = 3r + c):

op new id land neighbours successful unions islands
(0,1) 1 none 0 1
(1,0) 3 none 0 2
(1,2) 5 none 0 3
(2,1) 7 none 0 4
(1,1) 4 1, 7, 3, 5 4 4 + 1 - 4 = 1

The last row is the important one: four unions succeed because the four neighbours were four different islands.

Complexity. Time O(n · m + k · α(n · m)): creating the Disjoint Set is linear in the grid size, and each operation performs at most four unions of near-constant cost. Space O(n · m) for the Disjoint Set arrays and the land grid.

Approach 2 is an example of a general principle. When a structure only ever grows (edges or vertices are added, never removed), a Disjoint Set can maintain connectivity online at almost no cost. Deletions are what it cannot handle; for those, the usual trick is to process operations in reverse so that deletions become additions.

Edge cases and pitfalls