How hard is LeetCode 2307. Check for Contradictions in Equations?

LeetCode 2307. Check for Contradictions in Equations is rated Hard on LeetCode.

What topics does LeetCode 2307. Check for Contradictions in Equations cover?

LeetCode 2307. Check for Contradictions in Equations is tagged Depth-First Search, Union Find, Graph and Array on LeetCode.

Is LeetCode 2307. Check for Contradictions in Equations a premium problem?

Yes. LeetCode 2307. Check for Contradictions in Equations is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Check for Contradictions in Equations — LeetCode 2307 Python Solution

HardLeetCode PremiumDepth-First SearchUnion FindGraphArray

Problem: #2307
Pattern: Union-Find
Reading time: 5 min
Source: leetcode.com

The problem

You are given a 2D array of strings equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] means that Ai / Bi = values[i]. Determine if there exists a contradiction in the equations.

Example

Input: equations = [["a","b"],["b","c"],["a","c"]], values = [3,0.5,1.5]
Output: false
Explanation: The given equations are: a / b = 3, b / c = 0.5, a / c = 1.5

Python solution

Python

class Solution:
    def checkContradictions(
        self, equations: List[List[str]], values: List[float]
    ) -> bool:
        def find(x: int) -> int:
            if p[x] != x:
                root = find(p[x])
                w[x] *= w[p[x]]
                p[x] = root
            return p[x]

        d = defaultdict(int)
        n = 0
        for e in equations:
            for s in e:
                if s not in d:
                    d[s] = n
                    n += 1
        p = list(range(n))
        w = [1.0] * n
        eps = 1e-5
        for (a, b), v in zip(equations, values):
            a, b = d[a], d[b]
            pa, pb = find(a), find(b)
            if pa != pb:
                p[pb] = pa
                w[pb] = v * w[a] / w[b]
            elif abs(v * w[a] - w[b]) >= eps:
                return True
        return False

Complexity

Measure	Complexity
Time	O(n \times \log n) or O(n \times \alpha(n))
Space	O(n) auxiliary

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2307. Check for Contradictions in Equations 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.

Frequently asked questions

How hard is LeetCode 2307. Check for Contradictions in Equations?: LeetCode 2307. Check for Contradictions in Equations is rated Hard on LeetCode.
What topics does LeetCode 2307. Check for Contradictions in Equations cover?: LeetCode 2307. Check for Contradictions in Equations is tagged Depth-First Search, Union Find, Graph and Array on LeetCode.
Is LeetCode 2307. Check for Contradictions in Equations a premium problem?: Yes. LeetCode 2307. Check for Contradictions in Equations is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.