Problem of The Day: Evaluate Division
Problem Statement
My Solution [Accepted]
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
graph = defaultdict(list)
res = []
for i, (src, des) in enumerate(equations):
graph[src].append((des, values[i]))
graph[des].append((src, 1/values[i]))
def dfs(start, end):
stack = [(start, 1)]
visited = {start}
while stack:
node, ans = stack.pop()
if node == end:
return ans
for nei, val in graph[node]:
if nei not in visited:
stack.append((nei, ans * val))
visited.add(nei)
return -1
for src, des in queries:
if src in graph and des in graph:
res.append(dfs(src, des))
else:
res.append(-1)
return res
public class Solution
{
// Graph: node -> list of (neighbor, weight)
private Dictionary<string, List<(string, double)>> graph;
public double[] CalcEquation(
IList<IList<string>> equations,
double[] values,
IList<IList<string>> queries)
{
graph = new Dictionary<string, List<(string, double)>>();
// Build graph
for (int i = 0; i < equations.Count; i++)
{
string src = equations[i][0];
string dest = equations[i][1];
double val = values[i];
if (!graph.ContainsKey(src))
graph[src] = new List<(string, double)>();
if (!graph.ContainsKey(dest))
graph[dest] = new List<(string, double)>();
graph[src].Add((dest, val));
graph[dest].Add((src, 1.0 / val));
}
double[] result = new double[queries.Count];
// Process queries
for (int i = 0; i < queries.Count; i++)
{
string src = queries[i][0];
string dest = queries[i][1];
if (!graph.ContainsKey(src) || !graph.ContainsKey(dest))
{
result[i] = -1.0;
}
else
{
result[i] = Dfs(src, dest);
}
}
return result;
}
private double Dfs(string start, string end)
{
var stack = new Stack<(string node, double value)>();
var visited = new HashSet<string>();
stack.Push((start, 1.0));
visited.Add(start);
while (stack.Count > 0)
{
var (node, currVal) = stack.Pop();
if (node == end)
return currVal;
foreach (var (nei, weight) in graph[node])
{
if (!visited.Contains(nei))
{
visited.Add(nei);
stack.Push((nei, currVal * weight));
}
}
}
return -1.0;
}
}
Editorial
Approach 1: Path Search in Graph
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
graph = defaultdict(defaultdict)
def backtrack_evaluate(curr_node, target_node, acc_product, visited):
visited.add(curr_node)
ret = -1.0
neighbors = graph[curr_node]
if target_node in neighbors:
ret = acc_product * neighbors[target_node]
else:
for neighbor, value in neighbors.items():
if neighbor in visited:
continue
ret = backtrack_evaluate(
neighbor, target_node, acc_product * value, visited)
if ret != -1.0:
break
visited.remove(curr_node)
return ret
# Step 1). build the graph from the equations
for (dividend, divisor), value in zip(equations, values):
# add nodes and two edges into the graph
graph[dividend][divisor] = value
graph[divisor][dividend] = 1 / value
# Step 2). Evaluate each query via backtracking (DFS)
# by verifying if there exists a path from dividend to divisor
results = []
for dividend, divisor in queries:
if dividend not in graph or divisor not in graph:
# case 1): either node does not exist
ret = -1.0
elif dividend == divisor:
# case 2): origin and destination are the same node
ret = 1.0
else:
visited = set()
ret = backtrack_evaluate(dividend, divisor, 1, visited)
results.append(ret)
return results
Approach 2: Union-Find with Weights
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
gid_weight = {}
def find(node_id):
if node_id not in gid_weight:
gid_weight[node_id] = (node_id, 1)
group_id, node_weight = gid_weight[node_id]
# The above statements are equivalent to the following one
#group_id, node_weight = gid_weight.setdefault(node_id, (node_id, 1))
if group_id != node_id:
# found inconsistency, trigger chain update
new_group_id, group_weight = find(group_id)
gid_weight[node_id] = \
(new_group_id, node_weight * group_weight)
return gid_weight[node_id]
def union(dividend, divisor, value):
dividend_gid, dividend_weight = find(dividend)
divisor_gid, divisor_weight = find(divisor)
if dividend_gid != divisor_gid:
# merge the two groups together,
# by attaching the dividend group to the one of divisor
gid_weight[dividend_gid] = \
(divisor_gid, divisor_weight * value / dividend_weight)
# Step 1). build the union groups
for (dividend, divisor), value in zip(equations, values):
union(dividend, divisor, value)
results = []
# Step 2). run the evaluation, with "lazy" updates in find() function
for (dividend, divisor) in queries:
if dividend not in gid_weight or divisor not in gid_weight:
# case 1). at least one variable did not appear before
results.append(-1.0)
else:
dividend_gid, dividend_weight = find(dividend)
divisor_gid, divisor_weight = find(divisor)
if dividend_gid != divisor_gid:
# case 2). the variables do not belong to the same chain/group
results.append(-1.0)
else:
# case 3). there is a chain/path between the variables
results.append(dividend_weight / divisor_weight)
return results