399. Evaluate Division
Asked at Ripple, Uber
Difficulty
Medium
Time
O(e + q*(v+e))
Space
O(v+e)
Pattern
Array
Companies
2
Problem
You are given a list of division facts. Each fact says that one variable divided by another variable equals a known number. For example, a / b = 2.0 and b / c = 3.0.
You are also given a list of queries. Each query asks for the value of one variable divided by another, like a / c. Return a list with one answer per query, in the same order.
You can chain facts together. If a / b = 2 and b / c = 3, then a / c = 2 * 3 = 6. If two variables are not connected by any chain of facts, the answer is -1.0. Also, a variable divided by itself is always 1.0, even if that variable never appears in any fact. The input is guaranteed to have no contradictions and no division by zero.
Division facts form a chain
Constraints
- ●
1 <= equations.length <= 20 - ●
equations[i].length == 2 - ●
1 <= Ai.length, Bi.length <= 5 - ●
values.length == equations.length - ●
0.0 < values[i] <= 20.0 - ●
1 <= queries.length <= 20 - ●
queries[i].length == 2 - ●
1 <= Cj.length, Dj.length <= 5
Examples
equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]][6.00000,0.50000,-1.00000,1.00000,-1.00000]equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]][3.75000,0.40000,5.00000,0.20000]equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]][0.50000,2.00000,-1.00000,-1.00000]Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Ripple | Medium | View all Ripple questions → |
| Uber | Medium | View all Uber questions → |
How to Think About It
Graph modeling: each variable is a node. For a/b = k, add edge a->b with weight k and edge b->a with weight 1/k. For queries like c/d, find a path from c to d and multiply the edge weights along the way.
Why this works: a/b = 3 and b/c = 2 implies a/c = 6. In the graph, path a->b->c has weight 3 * 2 = 6. The path product equals the answer.
Algorithm: build the graph from equations. For each query, run BFS or DFS from the source to the target, tracking the running product. If the target is reached, return the product. If not, return -1.
Complexity: build graph in O(e) where e is number of equations. Each query: O(v + e) for BFS/DFS. Total: O(e + q*(v+e)) where q is number of queries and v is number of unique variables.
Optimal Approach
Build an adjacency list graph where each node is a variable. For equation a/b = k, add a->b with weight k and b->a with weight 1/k. For each query c/d, run BFS from c to d, tracking the running product of edge weights. Return the product if d is found, else -1.
Walkthrough with equations a/b=2, b/c=3, d/e=4 and query a/c:
- Graph: {a: [(b,2)], b: [(a,0.5),(c,3)], c: [(b,0.33)], d: [(e,4)], e: [(d,0.25)]}
- BFS from a: visit a, product=1
- Visit b from a: product = 1*2 = 2
- Visit c from b: product = 2*3 = 6. Found c. Return 6.
Query a/e: BFS from a reaches {a,b,c}. e is unreachable. Return -1.
Time: O(e + q*(v+e)). Space: O(v+e) for the graph.
Weighted graph + BFS product
What Trips People Up in Real Interviews
Forgetting the reverse edge. If a/b = k, you must also add b/a = 1/k. Without it, you cannot traverse from b to a, and queries like b/a will incorrectly return -1.
Not handling disconnected components. If c and d are not in the same connected component, return -1. The BFS/DFS naturally handles this by returning -1 if the target is not found.
Floating point precision. Multiplying many weights can cause precision issues. For this problem, comparing with a small epsilon (like 1e-9) is acceptable. In interviews, mention the precision concern.
Confusing this with a different equation type. This is division equations (a/b = k), not addition equations (a+b = k). Addition would require a different graph model (weighted sums).
Not checking if both variables in a query exist in the graph. If either variable was never seen in any equation, return -1 immediately.
Solution Code
O(e + q*(v+e)) timefrom collections import defaultdict, deque
def calcEquation(equations, values, queries):
graph = defaultdict(list)
for (a, b), val in zip(equations, values):
graph[a].append((b, val))
graph[b].append((a, 1.0 / val))
def bfs(start, end):
if start not in graph or end not in graph:
return -1.0
if start == end:
return 1.0
visited = {start}
queue = deque([(start, 1.0)])
while queue:
node, product = queue.popleft()
for neighbor, weight in graph[node]:
if neighbor == end:
return product * weight
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, product * weight))
return -1.0
return [bfs(s, e) for s, e in queries]Frequently Asked Questions
What is the Evaluate Division problem?
Given a set of equations (a/b = k) and queries (c/d), return the result of each query or -1 if no path exists. This problem models equations as a weighted graph where division becomes path multiplication.
How do you solve Evaluate Division?
The optimal approach runs in O(e + q*(v+e)) time and O(v+e) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Evaluate Division?
Evaluate Division is asked at Ripple, Uber. It is a medium difficulty problem.
What are common mistakes on Evaluate Division?
- Forgetting the reverse edge. If a/b = k, you must also add b/a = 1/k. Without it, you cannot traverse from b to a, and queries like b/a will incorrectly return -1.
- Not handling disconnected components. If c and d are not in the same connected component, return -1. The BFS/DFS naturally handles this by returning -1 if the target is not found.
- Floating point precision. Multiplying many weights can cause precision issues. For this problem, comparing with a small epsilon (like 1e-9) is acceptable. In interviews, mention the precision concern.
- Confusing this with a different equation type. This is division equations (a/b = k), not addition equations (a+b = k). Addition would require a different graph model (weighted sums).
- Not checking if both variables in a query exist in the graph. If either variable was never seen in any equation, return -1 immediately.