8ms C++ solution using Union Find with a dummy point


  • 7
    N

    My idea comes from the solution of Surrounded Regions.

    It's obvious to connect adjacent 1s. Then how to handle 0s?

    An interesting finding is that if we connect all 0s, then the count of UF is equal to the number of islands plus 1.

    class UF {
    public:
    	UF(int N) {
    		count = N;
    		id = new int[N];
    		weight = new int[N];
    		for (int i = 0; i < N; i++) {
    			id[i] = i;
    			weight[i] = 0;
    		}
    	}
    	~UF() {
    		delete[]id;
    		delete[]weight;
    	}
    	void unionP(int p, int q) {
    		int i = root(p);
    		int j = root(q);
    		if (i == j) {
    			return;
    		}
    		if (weight[i] < weight[j]) {
    			id[i] = j;
    		}
    		else if (weight[i] > weight[j]) {
    			id[j] = i;
    		}
    		else {
    			id[i] = j;
    			weight[j]++;
    		}
    		count--;
    	}
    	bool connected(int p, int q) {
    		return root(p) == root(q);
    	}
    	int getCount() {
    		return count;
    	}
    private:
    	int *id;
    	int *weight;
    	int count;
    	int root(int i) {
    		while (i != id[i]) {
    			id[i] = id[id[i]];
    			i = id[i];
    		}
    		return i;
    	}
    };
    
    class Solution {
    public:
    	// Runtime: 8 ms
    	int numIslands(vector<vector<char>>& grid) {
    		if (grid.empty() || grid[0].empty()) {
    			return 0;
    		}
    		int ROW = grid.size(), COL = grid[0].size();
    		UF uf(ROW * COL + 1);
    		int dummyPoint = ROW * COL; // We assume it as 0 and it connects all 0s.
    		for (int i = 0; i < ROW; i++) {
    			for (int j = 0; j < COL; j++) {
    				if (grid[i][j] == '1') {
    					if (j != COL - 1 && grid[i][j + 1] == '1') {
    						uf.unionP(i * COL + j, i * COL + j + 1);
    					}
    					if (i != ROW - 1 && grid[i + 1][j] == '1') {
    						uf.unionP(i * COL + j, (i + 1) * COL + j);
    					}
    				}
    				else {
    					uf.unionP(i * COL + j, dummyPoint);
    				}
    			}
    		}
    		return uf.getCount() - 1;
    	}
    };

  • 0
    E

    How about just keeping one counter for the number of 1s, and with each union, decrement the counter.


  • 0
    N

    is checking the neighbor on the left and neighbor above necessary? I see most of the solutions check them as well.


  • 1
    J

    I also use Union-Find, but just connect all the 1s. I use a map to store the mapping between position of 1s and the index in Union-Find. Here is the code.

    public class Solution {
    public int NumIslands(char[,] grid) {
        int m = grid.GetLength(0);
        int n = grid.GetLength(1);
        
        Dictionary<int, int> posMap = new Dictionary<int, int>();
        int count = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i,j] == '1') {
                    posMap.Add(i*n+j, count++);
                }
            }
        }
        
        UnionFind uf = new UnionFind(posMap.Count);
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                // right
                if(grid[i, j] == '1' && j+1<n && grid[i, j+1] == '1') {
                    uf.Union(posMap[i*n+j], posMap[i*n+j+1]);
                }
                // down
                if(grid[i, j] == '1' && i+1<m && grid[i+1, j] == '1') {
                    uf.Union(posMap[i*n+j], posMap[(i+1)*n+j]);
                }
            }
        }
        
        return uf.Count;
    }
    
    private class UnionFind
    {
        private int[] id;
        private int count;
        
        public UnionFind(int n) {
            count = n;
            id = new int[n];
            for(int i = 0; i < n; i++) {
                id[i] = i;
            }
        }
        
        public int Count { get { return count; } }
        
        public void Union(int p, int q) {
            var rootP = Find(p);
            var rootQ = Find(q);
            if(rootP == rootQ) return;
            
            id[rootP] = rootQ;
            count--;
        }
        
        public int Find(int i) {
            int root = i;
            while(id[root] != root) {
                root = id[root];
            }
            
            int p = i;
            while(id[p] != root) {
                var temp = id[p];
                id[p] = root;
                p = temp;
            }
            
            return root;
        }
        
        public bool Connected(int i, int j) {
            return Find(i) == Find(j);
        }
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.