18. Number of Islands II

Description

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.

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

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]

Idea

Use a union find data structure. Each time a one is inserted, make it its own parent, and add edges to its neighboring ones.

Solution

class UnionFind {
public:
    UnionFind(int m, int n) {
        count = 0, capacity = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                parent.push_back(-1);
                rank.push_back(0);
                capacity++;
            }
        }
    }
    
    int getParent(int node) {
        if (parent[node] != node) {
            parent[node] = getParent(parent[node]);
        }
        return parent[node];
    }
    
    bool contains(int node) {
        return (node >= 0) && (node < capacity) && parent[node] >= 0;
    }
    
    bool setParent(int node) {
        if (parent[node] < 0) {
            parent[node] = node;
            rank[node] = 1;
            count++;
            return true;
        }
        return false;
    }
    
    void join(int node1, int node2) {
        int group1 = getParent(node1);
        int group2 = getParent(node2);
        if (group1 != group2) {
            count--;
            // Join two groups
            int rank1 = rank[group1], rank2 = rank[group2];
            if (rank1 < rank2) {
                parent[group1] = group2;
            } else if (rank1 > rank2) {
                parent[group2] = group1;
            } else {
                parent[group1] = group2;
                rank[group2]++;
            }
        }
    }
    
    int getCount() {
        return count;
    }
    
private:
    int count;
    int capacity;
    vector<int> parent;
    vector<int> rank;
};

class Solution {
public:
    vector<int> numIslands2(int m, int n, vector<pair<int, int>> &positions) {
        UnionFind uf(m, n);
        vector<int> rtn;
        for (auto pos = positions.begin(); pos != positions.end(); ++pos) {
            int node = pos->first * n + pos->second;
            if (uf.setParent(node)) {
                if (node % n && uf.contains(node - 1)) uf.join(node, node - 1);
                if (uf.contains(node - n)) uf.join(node, node - n);
                if ((node + 1) % n && uf.contains(node + 1)) uf.join(node, node + 1);
                if (uf.contains(node + n)) uf.join(node, node + n);                
            }
            rtn.push_back(uf.getCount());
        }
        return rtn;
    }
};

158 / 158 test cases passed.
Runtime: 100 ms

18. Number of Islands II