# JAVA, 35 lines, O(1) for each query pair, nlogn for worst case preprocess time.

• Divide the strings in equations into connected sets.
If str1 and str2 are in same equation, they are connected.
Assign values to strings in a set based on the equations:
E.g. equation: a/b = V,

1. if a is in Set1 as Va and b is not in any set, then add b to Set1 as Va/V.
2. if b is in Set1 as Vb and a is not in any set, then add a to Set1 as Vb*V.
3. a,b not in any set, create new set, add a as V, b as 1.0.
4. if a is in Set1 as Va and b is in Set2 as Vb, join two sets.
(to achieve nlogn, need to join small to big, but no difference for existing TCs, n is # of equations)

Query: simply return Vx/Vy, if x and y are in the same set.

``````public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
Map<String, Integer> sets = new HashMap<>();
Map<String, Double> vals = new HashMap<>();
List<List<String>> list = new ArrayList<>();
for (int i = 0; i < equations.length; ++i) {
String a = equations[i][0], b = equations[i][1];
Integer setA = sets.get(a), setB = sets.get(b);
if (setA == null && setB == null) {
sets.put(a, list.size());
sets.put(b, list.size());
vals.put(a, values[i]);
vals.put(b, 1.0);
} else if (setB == null) {
sets.put(b, setA);
vals.put(b, vals.get(a) / values[i]); // not consider 0.0
} else if (setA == null) {
sets.put(a, setB);
vals.put(a, vals.get(b) * values[i]);
} else if (!setA.equals(setB)) {
double factor = vals.get(a) / values[i] / vals.get(b);
for (String str : list.get(setB)) {
sets.put(str, setA);
vals.put(str, vals.get(str) * factor);
}
}
}
double[] ans = new double[queries.length];
for (int i = 0; i < queries.length; ++i) {
Integer setA = sets.get(queries[i][0]), setB = sets.get(queries[i][1]);
if (setA != null && setA.equals(setB)) ans[i] = vals.get(queries[i][0]) / vals.get(queries[i][1]);
else ans[i] = -1.0;
}
return ans;
}
``````

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