MediumNo. 0399
Evaluate Division — LeetCode 399 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Breadth-First Search, Union Find, Graph, Array, String, Shortest Path
- On study lists
- LeetCode 75 and Top Interview 150
- Reading time
- 5 min
- Source
- leetcode.com
The problem
You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.
Example
- Input
- equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
- Output
- [6.00000,0.50000,-1.00000,1.00000,-1.00000]
- Explanation
- Given: a / b = 2.0, b / c = 3.0
Python solution
class Solution:
def calcEquation(
self, equations: List[List[str]], values: List[float], queries: List[List[str]]
) -> List[float]:
def find(x):
if p[x] != x:
origin = p[x]
p[x] = find(p[x])
w[x] *= w[origin]
return p[x]
w = defaultdict(lambda: 1)
p = defaultdict()
for a, b in equations:
p[a], p[b] = a, b
for i, v in enumerate(values):
a, b = equations[i]
pa, pb = find(a), find(b)
if pa == pb:
continue
p[pa] = pb
w[pa] = w[b] * v / w[a]
return [
-1 if c not in p or d not in p or find(c) != find(d) else w[c] / w[d]
for c, d in queries
]Complexity
- Time
- O(V+E)
- Space · auxiliary
- O(V)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 399. Evaluate Division is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0547 | Number of Provinces | Medium |
| 0684 | Redundant Connection | Medium |
| 0685 | Redundant Connection II | Hard |
| 0785 | Is Graph Bipartite? | Medium |
| 0886 | Possible Bipartition | Medium |
| 0990 | Satisfiability of Equality Equations | Medium |
Frequently asked questions
- How hard is LeetCode 399. Evaluate Division?
LeetCode 399. Evaluate Division is rated Medium on LeetCode.
- What is the time complexity of LeetCode 399. Evaluate Division?
The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 399. Evaluate Division?
The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 399. Evaluate Division cover?
LeetCode 399. Evaluate Division is tagged Depth-First Search, Breadth-First Search, Union Find, Graph, Array, String and Shortest Path on LeetCode.