305. Number of Islands II - cocoder39/coco39_LC GitHub Wiki

305. Number of Islands II

Notes 2021:

  • 每次添加一个land, count += 1
  • 每次合并两个land, count -= 1
  • find不影响count

注意duplicated operation

使用path compression + union by weight后，时间复杂度是O(M * log N) where M is number of operations (eg, union, find) and N is number of nodes in UF. In this case, M == K and N == K where K is len(positions)

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.size = {}
        self.count = 0
    
    def find(self, i):
        while i != self.parent[i]:
            i = self.parent[self.parent[i]]
        return i
    
    def add(self, i):
        self.parent[i] = i
        self.size[i] = 1
        self.count += 1
        
    def union(self, i, j):
        root1 = self.find(i)
        root2 = self.find(j)
        if root1 != root2:
            sz1, sz2 = self.size[root1], self.size[root2]
            if sz1 < sz2:
                self.parent[root1] = root2
                self.size[root2] = sz1 + sz2
            else:
                self.parent[root2] = root1
                self.size[root1] = sz1 + sz2
            self.count -= 1
    
    def getGroupSize(self):
        return self.count

class Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        lands = set()
        uf = UnionFind()
        
        res = []
        for position in map(tuple, positions):
            if position not in lands:
                uf.add(position)
                for dr, dc in DIRS:
                    newPosition = (position[0]+dr, position[1]+dc)
                    if newPosition in lands:
                        uf.union(position, newPosition)
            res.append(uf.getGroupSize())
            lands.add(position)
        return res

=======================================================

tips: unordered_set is not available for pair<int, int> because hash function for pair is not available

there are k connect() operations, and at most m * n elements in the UnionFind, where k is the length of positions. Regardless of initialization of UnionFind, time complexity is O(k log*(m*n))

class Solution {
public:
    class UnionFind {
    public:
        int num;
    
        UnionFind(int n) {
            num = 0;
            for (int i = 0; i < n; i++) {
                parent.push_back(i);
                sz.push_back(1);
            }
        }
        
        bool connected(int i, int j) {
            return root(i) == root(j);
        }
        
        void connect(int i, int j) {
            int p = root(i);
            int q = root(j);
            if (p == q) {
                return;
            } 
            
            if (sz[p] < sz[q]) {
                parent[p] = q;
                sz[q] += sz[p];
            } else {
                parent[q] = p;
                sz[p] += q; 
            }
            num--;
        }
        
    private:
        vector<int> parent;
        vector<int> sz;
        
        int root(int i) {
            while (i != parent[i]) {
                parent[i] = parent[parent[i]];
                i = parent[i];
            }
            return i;
        }
    };

    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
        vector<int> res;
        UnionFind uf(m * n);
        unordered_set<int> st;
        const vector<pair<int, int>> offsets{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
        for (auto position : positions) {
            int pos1 = position.first * n + position.second;
            uf.num++;
            for (auto offset : offsets) {
                int row = position.first + offset.first;
                int col = position.second + offset.second;
                int pos2 = row * n + col;
                if (row >= 0 && row < m && col >= 0 && col < n && st.find(pos2) != st.end()) {
                    uf.connect(pos1, pos2);
                }
            }
            st.insert(pos1);
            res.push_back(uf.num);
        }
        return res;
    }
};
⚠️ **GitHub.com Fallback** ⚠️