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

• 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))));
}
}
}
}
}
``````

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