Java Union-Find Beats 96%


  • 0
    J

    The idea is having an union-find data structure (implemented using hash map) to record all variables, using another hash map to record the relevant value for each variable. Every time we process an equation means equals to make a "union" operation, and we need to update relevant value for all the variables in the sets. We can check if two if variables have relationship and calculate value both in O(1) time.

    public class Solution {
        private HashMap<String, String> father = new HashMap<>();
        private HashMap<String, Double> valMap = new HashMap<>();
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            double[] result = new double[queries.length];
            if (values.length == 0 || result.length == 0) {
                return result;
            }
            
            for (int i = 0; i < values.length; i++) {
                String eq1 = equations[i][0];
                String eq2 = equations[i][1];
                if (!valMap.containsKey(eq1) && !valMap.containsKey(eq2)) {
                    father.put(eq1, eq1);
                    father.put(eq2, eq2);
                    valMap.put(eq1, values[i]);
                    valMap.put(eq2, 1.0);
                } else if (!valMap.containsKey(eq1)) {
                    father.put(eq1, eq1);
                    valMap.put(eq1, valMap.get(eq2) * values[i]);
                } else if (!valMap.containsKey(eq2)) {
                    father.put(eq2, eq2);
                    valMap.put(eq2, valMap.get(eq1) / values[i]);
                } else {
                    String fa = find(eq1);
                    for (String key: father.keySet()) {
                        if (find(key).equals(fa)) {
                            valMap.put(key, valMap.get(key) * values[i] * valMap.get(eq2));
                        }
                    }
                }
                union(eq1, eq2);
            }
            
            for (int i = 0; i < queries.length; i++) {
                if (!valMap.containsKey(queries[i][0]) || !valMap.containsKey(queries[i][1]) || !find(queries[i][0]).equals(find(queries[i][1]))) {
                    result[i] = -1.0;
                } else {
                    result[i] = valMap.get(queries[i][0]) / valMap.get(queries[i][1]);
                }
            }
            
            return result;
        }
        
        private void union(String a, String b) {
            String fa = find(a);
            String fb = find(b);
            if (!fa.equals(fb)) {
                father.put(fb, fa);
            }
        }
        
        private String find(String a) {
            String parent = father.get(a);
            while (!parent.equals(father.get(parent))) {
                parent = father.get(parent);
            }
            
            String tmp = "";
            String fa = father.get(a);
            while (!fa.equals(father.get(fa))) {
                tmp = father.get(fa);
                father.put(fa, parent);
                fa = tmp;
            }
            
            return parent;
        }
    }  
    

  • 0
    S

    The test cases for this question are very weak.
    This particular implementation doesn't work, but I think the idea is fine. The case when this fails is when eq1 and eq2 belong to different sets.
    Try the following test case:
    [ ["a","c"],["a","b"],["d","e"],["a","d"] ]
    [12.0,3.0,3.0,2.0]
    [ ["b","d"],["c","d"],["a","e"],["c","e"],["x","x"] ]


Log in to reply
 

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