[LeetCode] 721. Accounts Merge

 Problem : https://leetcode.com/problems/accounts-merge/

Use union-find to group email address of the same account.  Remember to sort the mail list in the end.

class UnionFind {
    int[] parent;
    
    UnionFind(int size) {
        parent = new int[size];
        
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }
    
    void union(int a, int b) {
        int ap = find(a);
        int bp = find(b);
        
        if (ap != bp) {
            parent[ap] = bp;
        }
    }
    
    int find(int a) {
        if (parent[a] == a) {
            return a;
        }
        
        parent[a] = find(parent[a]);
        
        return parent[a];
    }
}


class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        int ID = 0;
        
        // convert mail to ids
        HashMap<String, Integer> mailIds = new HashMap();
        HashMap<Integer, String> idToMail = new HashMap();
        HashMap<String, Integer> mailToName = new HashMap();
        
        for (int i = 0; i < accounts.size(); i++) {
            for (int j = 1; j < accounts.get(i).size(); j++) {
                if (mailIds.containsKey(accounts.get(i).get(j))) {
                    continue;
                }
                
                mailIds.put(accounts.get(i).get(j), ID);
                idToMail.put(ID, accounts.get(i).get(j));
                ID++;
                mailToName.put(accounts.get(i).get(j), i);
            }    
        }
        
        // use union-find to group mail ids
        UnionFind uf = new UnionFind(ID);
        
        for (int i = 0; i < accounts.size(); i++) {
            for (int j = 2; j < accounts.get(i).size(); j++) {
                uf.union(mailIds.get(accounts.get(i).get(j-1)), mailIds.get(accounts.get(i).get(j)));        
            }
        }
        
        // construct the mail list
        HashMap<Integer, List<String>> groups = new HashMap();
        
        for (int i = 0; i < ID; i++) {
            String email = idToMail.get(i);
       
            if (groups.containsKey(uf.find(i))) {
                groups.get(uf.find(i)).add(email);
            } else {
                List<String> emailList = new ArrayList();
                emailList.add(email);
                groups.put(uf.find(i), emailList);
            }
        }
        
        List<List<String>> result = new ArrayList();
        for (int pid : groups.keySet()) {
            List<String> list = new ArrayList();
            
            // sort mails
            Collections.sort(groups.get(pid));
            String name = accounts.get(mailToName.get(idToMail.get(pid))).get(0);
            
            list.add(name);
            list.addAll(groups.get(pid));
            result.add(list);
        }
        
        return result;
    }
}

[LeetCode] 565. Array Nesting

 Problem: https://leetcode.com/problems/array-nesting/

According to the given rule,  a valid set is built upon with the values of nums[k], nums[nums[k]], ...

We can use Union-Find to build set. Then return size of the largest set as result.

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
       
    def union(self, a, b):
        ap = self.find(a)
        bp = self.find(b)
        
        if ap != bp:
            self.parent[bp] = ap
     
    def find(self, a):
        if self.parent[a] != a:
            self.parent[a] = self.find(self.parent[a])
        return self.parent[a]

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        uf = UnionFind(len(nums))
        
        # build the sets
        for a, b in enumerate(nums):
            if a != b:
                uf.union(a, b)
        
        # get size of the largest set
        count = defaultdict(int)
        
        for i in range(len(nums)):
            count[uf.find(i)] += 1
        
        return max(count.values())

[LeetCode] 827. Making A Large Island

 Problem : https://leetcode.com/problems/making-a-large-island/

Consider an island is a group, it is intuitive to use union-find to find the size of islands then find the maximum size of island when join 2 disconnected islands together.

class UnionFind:
    def __init__(self, n):
        self.group = [i for i in range(n)]
        self.usize = defaultdict(lambda:1)
        
    def union(self, a, b):
        ap = self.find(a)
        bp = self.find(b)
        
        if ap != bp:
            self.group[bp] = ap
            self.usize[ap] += self.usize[bp]
            self.usize[bp] = 0
        
    
    def find(self, a):
        b = self.group[a]
        
        while b != self.group[b]:
            b = self.group[b]
        
        while self.group[a] != b:
            tmp = self.group[a]
            self.group[a] = b
            a = tmp
        
        return b
    
    def sizeOf(self, a):
        ap = self.find(a)
        return self.usize[ap]
            

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        ROW = len(grid)
        COLUMN = len(grid[0])
        
        uf = UnionFind(ROW * COLUMN)
        
        for y in range(ROW):
            for x in range(COLUMN):
                # union the adjucent '1's
                for dy, dx in [(-1,0), (0,-1)]:
                    ny, nx = y + dy, x + dx
                    if 0 <= ny < ROW and 0 <= nx < COLUMN and grid[ny][nx] == 1 and grid[y][x] == 1:
                        uf.union(ny*COLUMN + nx, y*COLUMN + x)
        
        result = 0
        for y in range(ROW):
            for x in range(COLUMN):
                if grid[y][x] == 1:
                    result = max(result, uf.sizeOf(y*COLUMN + x))
                else:
                    tmp = {}
                    # connect the disjointed unions
                    for dy, dx in [(-1,0), (1,0), (0,-1), (0,1)]:
                        ny, nx = y + dy, x + dx
                        if 0 <= ny < ROW and 0 <= nx < COLUMN and grid[ny][nx] == 1:
                            p = uf.find(ny * COLUMN + nx)
                            tmp[p] = uf.sizeOf(p)
                    
                    result = max(result, sum(tmp.values()) + 1)
        
        return result

[LeetCode] 128. Longest Consecutive Sequence

Problem : https://leetcode.com/problems/longest-consecutive-sequence/

Hash table based solution:

Store the input numbers in Set. Then lookup for consecutive sequence if current number does not have preceding number.

Time Complexity = O ( N )

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        memo = set(nums)
        
        result = 0
        
        for n in nums:
            if n - 1 not in memo:
                tmp = 1
            
                while n + 1 in memo:
                    tmp += 1
                    n += 1
            
                result = max(result, tmp)
        
        return result

Union-Find based solution:

Put the contiguous numbers in one group. Then find the maximum number of items in one group.

class UnionFind:
    def __init__(self, nums):
        self.memo = {}
        for n in nums:
            self.memo[n] = n
    
    def union(self, x, y):
        parent = y
        while parent != self.memo[parent]:
            tmp = self.memo[parent]
            self.memo[parent] = self.memo[x]
            parent = tmp
            
        self.memo[y] = self.memo[x]
    
    def find(self, x):
        if x not in self.memo:
            return None
        
        parent = self.memo[x]
        
        while self.memo[parent] != parent:
            parent = self.memo[parent]
    
        while self.memo[x] != parent:
            tmp = self.memo[x]
            self.memo[x] = parent
            x = tmp
            
        return parent

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        uf = UnionFind(nums)
        
        for n in nums:
            if uf.find(n-1) != None:
                uf.union(n-1, n)
            
            if uf.find(n+1) != None:
                uf.union(n, n+1)
        
        maxLength  = defaultdict(int)
        
        # count number of items in each group
        for k in uf.memo.keys():
            p = uf.find(k)
            maxLength[p] += 1
        
        return max(maxLength.values()) if maxLength.values() else 0