Evaluate Division

LeetCode Q 399 - Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0. queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? . return [6.0, 0.5, -1.0, 1.0, -1.0 ].

According to the example above:
equations = [ ["a", "b"], ["b", "c"] ], values = [2.0, 3.0], queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

Solution

Solution 1: Disjoint Set / Union Find

1. We use two maps, Map<String, String> root and Map<String, Double> dist.

   • root is used to store the divisors. For example, given a / b, in the root, we add two key value pairs, one is {a: b} and another is {b: b}.
   • dist is used to store the values. For example, given a / b = 2.0, in the root, we add two key value pairs, one is {a: 2.0} and another is {b: 1.0}.

2. In our algorithm, we implicitly utilzie Union Find data structure, doing ufs.union and ufs.find operations.

3. why dist.put(p1, values[i] * dist.get(e.get(1)) / dist.get(e.get(0)));
dist is a map that stores the “distance” (or factor) from current node to its root. Since we have e[i][0] = dist.get(e[i][0]) * r1 and e[i][1] = dist.get(e[i][1]) * r2, e[i][0] = e[i][1] * values[i] can be rewritten in dist.get(e[i][0]) * r1 = dist.get(e[i][1]) * r2 * values[i]. Then, we can get r1 = dist.get(e[i][1]) * r2 * values[i] / dist.get(e[i][0]). Since r2 = 1, r1 = dist.get(e[i][1]) * values[i] / dist.get(e[i][0]).

Code:

public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
	
	Map<String, String> root = new HashMap<>();
	Map<String, Double> dist = new HashMap<>();

	for (int i = 0; i < equations.size(); i++) {
		List<String> equ = equations.get(i);
		String p1 = find(root, dist, equ.get(0));
		String p2 = find(root, dist, equ.get(1));
		root.put(p1, p2);
		dist.put(p1, values[i] * dist.get(equ.get(1)) / dist.get(equ.get(0)));
	}

	double[] res = new double(queries.size());
	for (int i = 0; i < queries.size()) {
		List<String> que = queries.get(i);
		if (!root.containsKey(que(0)) || !root.containsKey(que(1))) {
			res[i] = -1.0; continue;
		} 
		String p1 = find(root, dist, que.get(0));
		String p2 = find(root, dist, que.get(1));
		if (!p1.equals(p2)) {
			res[i] = -1.0; continue;
		}
		res[i] = (double) dist.get(que.get(0)) / dist.get(que.get(1));
	}

	return res;
}

private String find (Map<String, String> root, Map<String, Double> dist, String s) {
	if (!root.containsKey(s)) {
		root.put(s, s); dist.put(s, 1.0); return s;
	}

	if (root.get(s).equals(s)) return s;

	int lastParent = root.get(s);
	int parent = find(root, dist, lastParent);

	root.put(s, parent);
	dist.put(s, dist.get(s) * dist.get(lastParent));

	return parent;
}

Solution 2: DFS

The DFS method is more straightforward.

Code:

public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
	
	Map<String, List<String>> map1 = new HashMap<>();
	Map<String, List<Double>> map2 = new HashMap<>();

	buildGraph(map1, map2, equations, values);

	double[] res = new double[queries.size()];
	for (int i = 0; i < queries.size(); i++) {
		res[i] = dfs(map1, map2, queries.get(i).get(0), 
		queries.get(i).get(1), new HashSet<String>(), 1.0);
	}
        
    return res;
}

private double dfs (Map<String, List<String>> map1, Map<String, List<Double>> map2, String start, String end, Set<String> visited, double res) {
	
	if (!map1.containsKey(start) || visited.contains(start)) 
		return -1.0;
	
	if (start.equals(end)) return res;

	visited.add(start);
	
	List<String> nexts = map1.get(start);
	List<Double> values = map2.get(start);

	int temp = -1.0;
	for (int i = 0; i < nexts.size(); i++) {
		String next = nexts.get(i);
		Double val = values.get(i);
		temp = dfs(map1, map2, next, end, viisted, res * values.get(i));
		if (temp != -1.0) break;
	}

	visited.remove(visited.size() - 1);
	return temp;
}

private void buildGraph(Map<String, List<String>> map1, Map<String, List<Double>> map2, List<List<String>> equations, double[] values) {
	for (int i = 0; i < equations.size(); i++) {
		List<String> equ = equations.get(i);
		if (!map1.containsKey(equ.get(0))) {
			map1.put(equ.get(0), new ArrayList<>());
			map2.put(equ.get(0), new ArrayList<>());
		}
		if (!map1.containsKey(equ.get(1))) {
			map1.put(equ.get(1), new ArrayList<>());
			map2.put(equ.get(1), new ArrayList<>());
		}
		
		map1.get(equ.get(0)).add(equ.get(1));
		map1.get(equ.get(1)).add(equ.get(0));
		map2.get(equ.get(0)).add(values[i]);
		map2.get(equ.get(1)).add(1 / values[i]);
	}
}