problemhardalgorithmsleetcode-2307leetcode 2307leetcode2307

Check for Contradictions in Equations

HardUpdated: Jul 1, 2025
Practice on:
LeetCode

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:

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:

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

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

Code

Java
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];
    }
}
Python
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)

Comments