1. Evaluate Division (LeetCode)
Model answer
The task
Given equations that define ratios between variables, answer queries asking for a ratio between two variables. Return -1.0 when the ratio cannot be determined.
Key idea
Represent each equation as two directed graph edges: from a to b with weight a / b, and from b to a with the reciprocal weight. A path’s edge weights multiply to give the ratio between its endpoints.
Approach
- Build a weighted adjacency list from the equations.
- For each query, return
-1.0if either variable is unknown. - Otherwise, use DFS to find a path between the variables, multiplying edge weights along the way.
- Track visited variables so cycles do not cause repeated exploration.
- If the variables are the same and known, the ratio is
1.0.
from collections import defaultdict
from typing import List
class Solution:
def calcEquation(
self,
equations: List[List[str]],
values: List[float],
queries: List[List[str]]
) -> List[float]:
graph = defaultdict(list)
for (numerator, denominator), value in zip(equations, values):
graph[numerator].append((denominator, value))
graph[denominator].append((numerator, 1.0 / value))
def find_ratio(start: str, target: str) -> float:
if start not in graph or target not in graph:
return -1.0
if start == target:
return 1.0
stack = [(start, 1.0)]
visited = {start}
while stack:
variable, product = stack.pop()
for neighbor, edge_value in graph[variable]:
if neighbor in visited:
continue
next_product = product * edge_value
if neighbor == target:
return next_product
visited.add(neighbor)
stack.append((neighbor, next_product))
return -1.0
return [find_ratio(a, b) for a, b in queries]
Complexity:
- Time: O(Q(V + E)), where each query may traverse the full graph.
- Space: O(V + E) for the graph and the DFS state.
Common follow-ups
- How can repeated queries be sped up? Use weighted union-find to answer each query in near-constant time after preprocessing.
- How would you handle inconsistent equations? Detect conflicting ratios when connecting variables or revisiting an already-connected pair.
- What if the graph is very large but queries are few? Keep DFS/BFS per query to avoid more elaborate preprocessing.