JAVA 3ms Union-Find Solution with only One HashMap, O(# of Nodes) Memory


  • 0
    D

    Just using the HashMap to store the nodes(String)'s parent and ratio to its parent in form of List. Normal Union-Find algorithm, with all nodes in same union directly points to a common parent.

    public class Solution {
        Map<String, List> buf = new HashMap<String, List>();
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            for(int i = 0;i<values.length;i++){   \\Read all edges
                Union(equations[i], values[i]);
            }
            for(String s:buf.keySet()){             \\Refresh the parents
                Find(s);
            }
            double[] ans = new double[queries.length];
            for(int i = 0;i<ans.length;i++){         \\Output the results
                if(!buf.containsKey(queries[i][0])||!buf.containsKey(queries[i][1])) ans[i] = -1.0;
                else if(queries[i][0].equals(queries[i][1])) ans[i] = 1.0;
                else if(!((String)buf.get(queries[i][0]).get(0)).equals((String)buf.get(queries[i][1]).get(0))) ans[i] = -1.0;
                else ans[i] = (double)buf.get(queries[i][0]).get(1)/(double)buf.get(queries[i][1]).get(1);
            }
            return ans;
        }
        private void Find(String s){                    \\ Function for finding or refreshing one step parent
            String t = (String)buf.get(s).get(0);
            if(s!=t){
                Find(t);
                buf.put(s, new ArrayList(Arrays.asList((String)buf.get(t).get(0),(double)buf.get(s).get(1)*(double)buf.get(t).get(1))));
            }
        }
        private void Union(String[] eq, double x){  \\ Union
            if(!buf.containsKey(eq[0])){
                if(!buf.containsKey(eq[1])){
                    buf.put(eq[1], new ArrayList(Arrays.asList(eq[1], 1.0)));                
                }
                buf.put(eq[0], new ArrayList(Arrays.asList(eq[1],x)));
            }
            else{
                if(!buf.containsKey(eq[1])){
                    buf.put(eq[1], new ArrayList(Arrays.asList(eq[0], 1.0/x)));                
                }
                else{
                    Find(eq[0]);
                    Find(eq[1]);
                    if(!((String)buf.get(eq[0]).get(0)).equals((String)buf.get(eq[1]).get(0))){ \\ Merge 2 groups
                        buf.put((String)buf.get(eq[0]).get(0), new ArrayList(Arrays.asList((String)buf.get(eq[1]).get(0),1.0/((double)buf.get(eq[0]).get(1))*x*(double)buf.get(eq[1]).get(1))));
                        buf.put(eq[0], new ArrayList(Arrays.asList((String)buf.get(eq[1]).get(0),x*(double)buf.get(eq[1]).get(1))));
                    }
                }
            }
        }
    }
    

Log in to reply
 

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