Check for Contradictions in Equations

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. Return true if there is a contradiction, orfalse otherwise.

Note :

When checking if two numbers are equal, check that their absolute difference is less than 10-5.
The testcases are generated such that there are no cases targeting precision, i.e. using double is enough to solve the problem.

Examples

Example 1:

1
2
3
4
5


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
There are no contradictions in the equations. One possible assignment to satisfy all equations is:
a = 3, b = 1 and c = 2.

Example 2:

1
2
3
4
5
6


Input: equations = [["le","et"],["le","code"],["code","et"]], values = [2,5,0.5]
Output: true
Explanation:
The given equations are: le / et = 2, le / code = 5, code / et = 0.5
Based on the first two equations, we get code / et = 0.4.
Since the third equation is code / et = 0.5, we get a contradiction.

Constraints:

1 <= equations.length <= 100
equations[i].length == 2
1 <= Ai.length, Bi.length <= 5
Ai, Bi consist of lowercase English letters.
equations.length == values.length
0.0 < values[i] <= 10.0
values[i] has a maximum of 2 decimal places.

Solution

Method 1 – Union Find with Weighted Edges

Intuition: We treat each variable as a node in a graph, and each equation as a weighted edge. We use union-find (disjoint set) with path compression and weight tracking to maintain the ratio between variables. If we find a contradiction (i.e., two variables are already connected but the ratio does not match), we return true.

Approach:

Map each variable to an integer id.
Use union-find with a parent array and a weight array, where weight[i] is the ratio between i and its parent.
For each equation, union the two variables and check for contradiction.
When uniting, if the variables are already connected, check if the ratio matches (within 1e-5).
If a contradiction is found, return true. Otherwise, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


class Solution {
    public boolean checkContradictions(String[][] equations, double[] values) {
        Map<String, Integer> id = new HashMap<>();
        int n = 0;
        for (String[] eq : equations) {
            if (!id.containsKey(eq[0])) id.put(eq[0], n++);
            if (!id.containsKey(eq[1])) id.put(eq[1], n++);
        }
        int[] p = new int[n];
        double[] w = new double[n];
        for (int i = 0; i < n; i++) { p[i] = i; w[i] = 1.0; }
        for (int i = 0; i < equations.length; i++) {
            int x = id.get(equations[i][0]), y = id.get(equations[i][1]);
            double v = values[i];
            int px = find(p, w, x), py = find(p, w, y);
            if (px == py) {
                if (Math.abs(w[x] / w[y] - v) > 1e-5) return true;
            } else {
                p[px] = py;
                w[px] = w[y] * v / w[x];
            }
        }
        return false;
    }
    private int find(int[] p, double[] w, int x) {
        if (p[x] != x) {
            int orig = p[x];
            p[x] = find(p, w, p[x]);
            w[x] *= w[orig];
        }
        return p[x];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution:
    def checkContradictions(self, equations: list[list[str]], values: list[float]) -> bool:
        id = {}
        n = 0
        for a, b in equations:
            if a not in id:
                id[a] = n
                n += 1
            if b not in id:
                id[b] = n
                n += 1
        p = list(range(n))
        w = [1.0] * n
        def find(x):
            if p[x] != x:
                orig = p[x]
                p[x] = find(p[x])
                w[x] *= w[orig]
            return p[x]
        for (a, b), v in zip(equations, values):
            x, y = id[a], id[b]
            px, py = find(x), find(y)
            if px == py:
                if abs(w[x] / w[y] - v) > 1e-5:
                    return True
            else:
                p[px] = py
                w[px] = w[y] * v / w[x]
        return False

Complexity

⏰ Time complexity: O(N log N), where N is the number of equations.
🧺 Space complexity: O(N)

Problem#

Examples#

Solution#

Method 1 – Union Find with Weighted Edges#

Code#

Complexity#