Problem

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Examples

Example 1

1
2

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

Explanation:

Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

1
2
3

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1
2
3

1 0 0
0 0 0   Number of islands = 1
0 0 0

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1
2
3

1 1 0
0 0 0   Number of islands = 1
0 0 0

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1
2
3

1 1 0
0 0 1   Number of islands = 2
0 0 0

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1
2
3

1 1 0
0 0 1   Number of islands = 3
0 1 0

Follow up

Can you do it in time complexity O(k log mn), where k is the length of the positions?

Solution

Method 1 – Union Find (Disjoint Set Union)

Intuition

We use a Union Find (Disjoint Set Union) data structure to efficiently keep track of connected components (islands) as we add land to the grid. Each new land cell is initially its own island, but if it is adjacent to another land cell, we merge their sets, reducing the island count. This approach allows us to dynamically maintain the number of islands after each operation in nearly constant time.

Approach

  1. Initialize a parent array of size m * n with all values set to -1 (representing water).
  2. For each position in positions, convert it to a 1D index and set its parent to itself (mark as land). Increment the island count.
  3. For each of the 4 directions, check if the neighboring cell is land (parent not -1). If so, find its root. If the root is different from the current cell’s root, union them and decrement the island count.
  4. After processing each position, record the current island count.
  5. Return the list of island counts after each operation.

Complexity

  • ⏰ Time complexity: O(k * α(mn)), where k is the number of positions and α is the inverse Ackermann function (nearly constant for practical input sizes).
  • 🧺 Space complexity: O(m * n), for the parent array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        int[] parent = new int[m * n];
        Arrays.fill(parent, -1);
        List<Integer> ans = new ArrayList<>();
        int count = 0;
        int[][] dirs = {{-1,0},{0,1},{1,0},{0,-1}};
        for (int[] pos : positions) {
            int r = pos[0], c = pos[1], idx = r * n + c;
            if (parent[idx] != -1) {
                ans.add(count); continue;
            }
            parent[idx] = idx;
            count++;
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1], nidx = nr * n + nc;
                if (nr < 0 || nc < 0 || nr >= m || nc >= n || parent[nidx] == -1) continue;
                int root1 = find(parent, idx), root2 = find(parent, nidx);
                if (root1 != root2) {
                    parent[root2] = root1;
                    count--;
                }
            }
            ans.add(count);
        }
        return ans;
    }
    private int find(int[] parent, int i) {
        if (parent[i] != i) parent[i] = find(parent, parent[i]);
        return parent[i];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
        vector<int> parent(m * n, -1), ans;
        int count = 0;
        vector<pair<int,int>> dirs = {{-1,0},{0,1},{1,0},{0,-1}};
        for (auto& pos : positions) {
            int r = pos[0], c = pos[1], idx = r * n + c;
            if (parent[idx] != -1) { ans.push_back(count); continue; }
            parent[idx] = idx;
            count++;
            for (auto& d : dirs) {
                int nr = r + d.first, nc = c + d.second, nidx = nr * n + nc;
                if (nr < 0 || nc < 0 || nr >= m || nc >= n || parent[nidx] == -1) continue;
                int root1 = find(parent, idx), root2 = find(parent, nidx);
                if (root1 != root2) {
                    parent[root2] = root1;
                    count--;
                }
            }
            ans.push_back(count);
        }
        return ans;
    }
    int find(vector<int>& parent, int i) {
        if (parent[i] != i) parent[i] = find(parent, parent[i]);
        return parent[i];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def numIslands2(self, m: int, n: int, positions: list[list[int]]) -> list[int]:
        parent = [-1] * (m * n)
        ans = []
        count = 0
        def find(i):
            if parent[i] != i:
                parent[i] = find(parent[i])
            return parent[i]
        for r, c in positions:
            idx = r * n + c
            if parent[idx] != -1:
                ans.append(count)
                continue
            parent[idx] = idx
            count += 1
            for dr, dc in [(-1,0),(0,1),(1,0),(0,-1)]:
                nr, nc = r + dr, c + dc
                nidx = nr * n + nc
                if 0 <= nr < m and 0 <= nc < n and parent[nidx] != -1:
                    root1, root2 = find(idx), find(nidx)
                    if root1 != root2:
                        parent[root2] = root1
                        count -= 1
            ans.append(count)
        return ans