Solution with union find algorithm


  • 1
    K

    Connect all water with one single end unit (m * n), and connect all land with its neighboring lands.

    public class Solution {
        public int numIslands(char[][] grid) {
            int m = grid.length;
            if(m <= 0) return 0;
            int n = grid[0].length;
            UF iUnion = new UF(m * n + 1);
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    if(grid[i][j] == '0') iUnion.connect(i * n + j, m * n);
                    else{
                    	if(j < n - 1 && grid[i][j + 1] == '1') iUnion.connect(i * n + j, i * n + j + 1);
                    	if(i < m - 1 && grid[i + 1][j] == '1') iUnion.connect(i * n + j, i * n + j + n);
                    }
                }
            }
            return iUnion.size() - 1; 
        }
        
        class UF{
            private int[] weight;
            private int[] uid;
            private int size;
            public UF(int capacity){
                weight = new int[capacity];
                uid = new int[capacity];
                size = capacity;
                for(int i = 0; i < capacity; i++){
                  uid[i] = i;
                  weight[i] = 1;
                }
            }
            
            public int size(){
                return size;
            }
            
            public int find(int p){
                int start = p, tmp;
                while(uid[p] != p){
                    p = uid[p];
                }
                // path compression
                while(uid[start] != p){
                    tmp = uid[start];
                    uid[start] = p;
                    start = tmp;
                }
                return p;
            }
            
            public boolean connected(int p, int q){
                return find(p) == find(q);
            }
            
            public void connect(int p, int q){
                int pid = find(p);
                int qid = find(q);
                if(pid == qid) return;
                if(weight[pid] > weight[qid]){
                    uid[qid] = pid;
                    weight[pid] += weight[qid];
                }else{
                    uid[pid] = qid;
                    weight[qid] += weight[pid];
                }
                size--;
            }
        }
    }

  • 1
    D

    If UF has a member method to decrease its size, there is no need to connect "water" to dummy node -- you can simply decrease size for a "water" grid.

    Below is my Python solution using the same idea.

    class DisjointSet(object):
        def __init__(self, count):
            # use list as parents and ranks
            self.rank   = [0] * count
            self.parent = range(count + 1)
            self.size   = count
    
        def find(self, x):
            # path compression
            while self.parent[x] != x:
                self.parent[x] = self.parent[self.parent[x]]
                x = self.parent[x]
            return x
    
        def union(self, x, y):
            # union by rank
            x, y = self.find(x), self.find(y)
            if x != y:
                self.size -= 1
                if self.rank[x] > self.rank[y]:
                    self.parent[y] = x
                else:
                    self.parent[x] = y
                    if self.rank[x] == self.rank[y]:
                        self.rank[y] += 1
    
    class Solution(object):
        def numIslands(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            num_island, rows = 0, len(grid)
            if rows > 0:
                cols = len(grid[0])
                ds = DisjointSet(rows*cols)
                for x in xrange(rows):
                    for y in xrange(cols):
                        if grid[x][y] == '0':
                            # decrease size if current cell is water
                            ds.size -= 1
                        else:
                            # check and union with north / west cells if they are land
                            index = x*cols + y
                            if x-1 >= 0 and grid[x-1][y] == '1':
                                ds.union(index, index - cols)
                            y -= 1
                            if y >= 0 and grid[x][y] == '1':
                                ds.union(index, index-1)
                num_island = ds.size
    
            return num_island
    

Log in to reply
 

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