305. Number of Islands II (Hard)

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.

Example:

Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]. Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

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 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 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 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 1 0
0 0 1   Number of islands = 3
0 1 0

We return the result as an array: [1, 1, 2, 3]

Solution: Union Find

version 1: 109ms

当union的两个岛不属于同一个root时，count减一。

class Solution {
    void Union(int* arr, int a, int b, int& count) {
        int r1 = find(arr, a), r2 = find(arr, b);
        if (r1 != r2) {
            --count;
            arr[r1] = r2;
        }
    }
    int find(int* arr, int a) {
        while (arr[a] != a) a = arr[a];
        return a;
    }
public:
    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
        vector<int> res;
        vector<vector<bool>> map(m, vector<bool>(n, false));
        int arr[m*n];
        for (int i = 0; i < m*n; ++i) {
            arr[i] = i;
        }
        vector<int> dirs = {0,-1,0,1,0};
        int count = 0;

        for (auto& pos: positions) {
            int i = pos.first, j = pos.second;
            map[i][j] = true;

            int id = i*n+j;
            ++count;
            for (int k = 0; k < 4; ++k) {
                int x = i+dirs[k], y = j+dirs[k+1];
                if (x >= 0 && x < m && y >= 0 && y < n && map[x][y]) {
                    Union(arr, id, x*n+y, count);
                }
            }
            res.push_back(count);
        }

        return res;
    }
};

version 2: 119ms

class Solution {
    void Union(int* arr, int a, int b, int& count) {
        int r1 = find(arr, a), r2 = find(arr, b);
        if (r1 != r2) {
            --count;
            arr[r1] = r2;
        }
    }
    int find(int* arr, int a) {
        while (arr[a] != a) {
            // compress tree: arr[a] = arr[arr[a]];
            a = arr[a];
        }
        return a;
    }
public:
    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
        vector<int> res;
        int arr[m*n];
        for (int i = 0; i < m*n; ++i) {
            arr[i] = -1;
        }
        vector<int> dirs = {0,-1,0,1,0};
        int count = 0;

        for (auto& pos: positions) {
            int i = pos.first, j = pos.second;
            int id = i*n+j;
            arr[id] = id;

            ++count;
            for (int k = 0; k < 4; ++k) {
                int x = i+dirs[k], y = j+dirs[k+1];
                int cur_id = x*n+y;
                if (x >= 0 && x < m && y >= 0 && y < n && arr[cur_id] != -1) {
                    Union(arr, id, cur_id, count);
                }
            }
            res.push_back(count);
        }

        return res;
    }
};