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

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

PythonSolution
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

Related problems
No.ProblemDifficulty
0547Number of ProvincesMedium
0684Redundant ConnectionMedium
0685Redundant Connection IIHard
0785Is Graph Bipartite?Medium
0886Possible BipartitionMedium
0990Satisfiability of Equality EquationsMedium

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.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.