Command Palette

Search for a command to run...

Hectal
Problem 25.6 · Union-Find (DSU)Hard

Number of Islands II

PatternUnion-FindMatrix Traversal

What it teaches: Dynamic connectivity: land appears one cell at a time and the island count is reported after each.

Practise it on judges as “Number of Islands II”.

The problem

An m × n grid starts as water. positions[i] = [r, c] turns that cell into land. After each operation, return the number of islands (4-directional). A position may repeat.

Example 1

Input: m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
Output: [1, 1, 2, 3]

Constraints

  • 1 ≤ m, n, positions ≤ 10⁴
  • m × n ≤ 10⁴

Pattern clues in the wording

  • → Count after every addition

These clues point to Union-Find: Keep each group as a tree with a root; find the root to test membership and link roots to merge groups.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
m = 3
n = 3
positions = [[0,0],[0,1],[1,2],[2,1]]
[1,1,2,3]
2
m = 1
n = 1
positions = [[0,0]]
[1]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Union-find over cells · O(k α(mn))
1

Union-find over cells

Time O(k α(mn)) Space O(mn)

parent[r × n + c] = −1 for water. Adding land creates its own set; union with land neighbours; record the count.

Approach 1
import java.util.*;

class Solution {
    private int[] parent;

    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        parent = new int[m * n];
        Arrays.fill(parent, -1);
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        List<Integer> out = new ArrayList<>();
        int count = 0;
        for (int[] p : positions) {
            int id = p[0] * n + p[1];
            if (parent[id] == -1) {
                parent[id] = id;
                count++;
                for (int[] d : dirs) {
                    int r = p[0] + d[0], c = p[1] + d[1];
                    if (r < 0 || c < 0 || r >= m || c >= n || parent[r * n + c] == -1) continue;
                    int a = find(id), b = find(r * n + c);
                    if (a != b) { parent[a] = b; count--; }
                }
            }
            out.add(count);
        }
        return out;
    }

    private int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
}

Verdict: BFS after each addition would be O(k × mn).

Before you submit

Edge cases and common mistakes

Test these inputs

  • Repeated position
  • New cell joining three islands at once

Mistakes people make

  • Counting a repeated position as a new island.

Interview

Follow-up questions

What if land could also turn back into water?