Java, Union-Find & Ranking & Path Compression, most efficient algorithm


  • 0
    H

    I had this question in a G interview. Linking parents will give you O(logn) for find operation, however, using path compression, it becomes constant time.

    class Solution {
        class Node {
            int rank;
            Node parent; 
            double ratio;
            String val;
            public Node(String val) {
                this.val = val;
            }
        }
        class Result {
            Node parent;
            double ratio;
        }
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            HashMap<String, Node> map = new HashMap();
            
            for (int i = 0; i < equations.length; i++) {
                String s1 = equations[i][0];
                String s2 = equations[i][1];
                
                Node n1 = map.getOrDefault(s1, new Node(s1));
                Node n2 = map.getOrDefault(s2, new Node(s2));
                map.put(s1, n1);
                map.put(s2, n2);
                
                union(n1, n2, values[i]);
                
            }
            
            double[] ret = new double[queries.length];
            for (int i = 0; i < queries.length; i++) {
                Node n1 = map.get(queries[i][0]);
                Node n2 = map.get(queries[i][1]);
                
                if (n1 == null || n2 == null) {
                    ret[i] = -1;
                    continue;
                }
                
                Result n1res = findParentAndRatio(n1);
                Result n2res = findParentAndRatio(n2);
                if (n2res.parent != n1res.parent) {
                    ret[i] = -1;
                } else {
                    ret[i] = (n1res.ratio) * (1/n2res.ratio);
                }
            }
            
            return ret;
        }
        
        public void union(Node n1, Node n2, double val) {
            if (n1.parent == null) {
                n1.parent = n1;
                n1.ratio = 1;
            }
            if (n2.parent == null) {
                n2.parent = n2;
                n2.ratio = 1;
            }
            Result n1res = findParentAndRatio(n1);
            Result n2res = findParentAndRatio(n2);
            
            if (n1res.parent == n2res.parent) {
                return; // no need
            }
            
            if (n2res.parent.rank > n1res.parent.rank) {
                Node temp = n2;
                n2 = n1;
                n1 = temp;
                Result tempRes = n2res;
                n2res = n1res;
                n1res = tempRes;
                val = 1/val;
            }
            
            n2.parent = n1res.parent;
            n2.ratio = n1res.ratio * (1/val);
            n1res.parent.rank++;
        }
        
        public Result findParentAndRatio(Node n) {
            double ratio = 1;
            Node cur = n;
            
            while (cur != cur.parent) {
                ratio *= cur.ratio;
                cur = cur.parent;
            }
            
            Result res = new Result();
            
            res.ratio = ratio;
            res.parent = cur;
            
            //path compresion
            n.ratio = res.ratio;
            n.parent = res.parent;
            return res;
        }
    }
    
    

Log in to reply
 

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