LeetCode 2307 - Check for Contradictions in Equations

Difficulty: 🔴 Hard
Topics: Array, Depth-First Search, Union-Find, Graph Theory

Solution

Problem Understanding

This problem gives us a collection of equations of the form:

$$A_i / B_i = value_i$$

Each variable is represented as a string, and each equation defines a multiplicative relationship between two variables.

The task is to determine whether all equations can simultaneously be true. If at least one equation conflicts with the others, we return true because a contradiction exists. Otherwise, we return false.

For example, if we know:

$$a / b = 2$$

and

$$b / c = 3$$

then logically:

$$a / c = 6$$

If another equation says:

$$a / c = 5$$

then the system is inconsistent, so a contradiction exists.

The important observation is that these equations form a graph of ratios. Every variable can be connected to others through multiplicative relationships. Whenever two variables are already connected, their ratio is already implied by previously processed equations. If a new equation disagrees with that implied ratio, we have found a contradiction.

The constraints are relatively small, with at most 100 equations, so even graph traversal approaches are feasible. However, we still want an efficient and clean solution.

There are several important edge cases:

Variables may appear for the first time at any point in the input.
Multiple disconnected groups of equations may exist.
A contradiction may occur immediately or only after many equations are chained together.
Floating point precision matters, so comparisons must use an epsilon tolerance of 1e-5.
Equations may indirectly imply ratios across long chains of variables.

Approaches

Brute Force Approach

A straightforward solution is to treat the equations as a graph and, for every new equation, run a DFS or BFS to see whether a path already exists between the two variables.

If a path exists, we compute the implied ratio by multiplying edge weights along the path. Then we compare that implied ratio with the new equation's value.

If they differ by more than 1e-5, we found a contradiction.

If no path exists, we simply add the equation to the graph.

This approach is correct because graph traversal explores all multiplicative relationships implied by earlier equations.

However, repeatedly searching the graph for every equation is inefficient. With $n$ equations, each DFS may visit many nodes and edges, leading to quadratic complexity.

Optimal Approach, Weighted Union-Find

The key insight is that this problem is fundamentally about maintaining connected components and relative ratios between variables.

Union-Find is ideal for tracking connected components efficiently. A weighted Union-Find extends the idea by storing multiplicative weights between nodes and their parents.

For every variable:

parent[x] stores the representative parent.
weight[x] stores the ratio:

$$x / parent[x]$$

Using path compression, we can derive:

$$x / root$$

for every variable.

When processing an equation:

$$a / b = value$$

there are two cases:

a and b belong to different components.

We merge the components while preserving the ratio relationship. 2. a and b already belong to the same component.

Then their ratio is already implied by previous equations. We compute the implied ratio and compare it with value.

This approach is both elegant and efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	DFS/BFS for each equation
Optimal	O(n α(n))	O(n)	Weighted Union-Find with path compression

Algorithm Walkthrough

Create two hash maps:

parent[x] stores the parent of variable x
weight[x] stores the ratio:

$$x / parent[x]$$

When a variable appears for the first time, initialize:

parent[x] = x
weight[x] = 1.0

This means each variable initially forms its own component. 2. Implement a find(x) function.

This function recursively finds the root of x.

During path compression, we update the weight so that after compression:

$$weight[x] = x / root$$

This is critical because it lets us quickly compute ratios between connected variables.

Process each equation:

$$a / b = value$$

Find the roots of a and b.

Let:

rootA be the root of a
rootB be the root of b

If the roots are the same, the ratio between a and b is already known.

Since:

$$a / root = weight[a]$$

and

$$b / root = weight[b]$$

then:

$$a / b = weight[a] / weight[b]$$

Compare this computed ratio with value.

If the absolute difference exceeds 1e-5, return true.

If the roots are different, merge the components.

We attach one root under the other while preserving the equation relationship.

Suppose we attach rootA under rootB.

We need:

$$a / b = value$$

Since:

$$a / rootA = weight[a]$$

and

$$b / rootB = weight[b]$$

we derive:

$$rootA / rootB = \frac{value \cdot weight[b]}{weight[a]}$$

Store this ratio in weight[rootA].

If all equations are processed without conflicts, return false.

Why it works

The Union-Find structure maintains a consistent multiplicative relationship between every node and its component root.

At any moment:

$$weight[x] = x / root(x)$$

Therefore, for any connected variables:

$$x / y = \frac{x/root}{y/root}$$

When a new equation connects already-related variables, the algorithm checks whether the implied ratio matches the provided ratio. If not, the equations are inconsistent.

Because path compression preserves these relationships correctly, all ratio computations remain valid throughout execution.

Python Solution

from typing import List

class Solution:
    def checkContradictions(self, equations: List[List[str]], values: List[float]) -> bool:
        parent = {}
        weight = {}

        def find(x: str) -> str:
            if parent[x] != x:
                original_parent = parent[x]
                root = find(original_parent)

                weight[x] *= weight[original_parent]
                parent[x] = root

            return parent[x]

        for (a, b), value in zip(equations, values):

            if a not in parent:
                parent[a] = a
                weight[a] = 1.0

            if b not in parent:
                parent[b] = b
                weight[b] = 1.0

            root_a = find(a)
            root_b = find(b)

            if root_a == root_b:
                implied = weight[a] / weight[b]

                if abs(implied - value) >= 1e-5:
                    return True
            else:
                parent[root_a] = root_b

                weight[root_a] = (
                    value * weight[b] / weight[a]
                )

        return False

The implementation starts by maintaining two dictionaries, parent and weight.

The find function performs path compression while simultaneously updating multiplicative weights. This is the most important part of the solution because it ensures that after compression, each node directly stores its ratio relative to the root.

During equation processing, new variables are initialized lazily when first encountered.

If two variables already belong to the same connected component, the algorithm computes the implied ratio using:

$$weight[a] / weight[b]$$

and checks whether it matches the provided value within the allowed tolerance.

If the variables belong to different components, the union step merges the trees while preserving the multiplicative relationship between the roots.

Finally, if no contradiction is found after processing all equations, the function returns False.

Go Solution

package main

import "math"

func checkContradictions(equations [][]string, values []float64) bool {
	parent := make(map[string]string)
	weight := make(map[string]float64)

	var find func(string) string

	find = func(x string) string {
		if parent[x] != x {
			originalParent := parent[x]
			root := find(originalParent)

			weight[x] *= weight[originalParent]
			parent[x] = root
		}

		return parent[x]
	}

	for i, eq := range equations {
		a := eq[0]
		b := eq[1]
		value := values[i]

		if _, exists := parent[a]; !exists {
			parent[a] = a
			weight[a] = 1.0
		}

		if _, exists := parent[b]; !exists {
			parent[b] = b
			weight[b] = 1.0
		}

		rootA := find(a)
		rootB := find(b)

		if rootA == rootB {
			implied := weight[a] / weight[b]

			if math.Abs(implied-value) >= 1e-5 {
				return true
			}
		} else {
			parent[rootA] = rootB

			weight[rootA] = value * weight[b] / weight[a]
		}
	}

	return false
}

The Go implementation follows the same logic as the Python version.

Go requires explicit map initialization and existence checks using the two-value map lookup syntax.

The recursive find function is implemented using a function variable so it can reference itself recursively.

Floating point comparison uses math.Abs.

Because Go maps return zero values for missing keys, explicit existence checks are important before initialization.

Worked Examples

Example 1

Input:

equations = [["a","b"],["b","c"],["a","c"]]
values = [3,0.5,1.5]

Initial state:

Variable	Parent	Weight
none	none	none

Processing `a / b = 3`

Initialize variables.

Variable	Parent	Weight
a	a	1
b	b	1

Union a under b.

$$weight[a] = 3 \times 1 / 1 = 3$$

Updated state:

Variable	Parent	Weight
a	b	3
b	b	1

This means:

$$a / b = 3$$

Processing `b / c = 0.5`

Initialize c.

Variable	Parent	Weight
c	c	1

Union b under c.

$$weight[b] = 0.5$$

Updated state:

Variable	Parent	Weight
a	b	3
b	c	0.5
c	c	1

Now:

$$a / c = 3 \times 0.5 = 1.5$$

Processing `a / c = 1.5`

Find compresses paths:

$$weight[a] = 1.5$$

Computed ratio:

$$a / c = weight[a] / weight[c] = 1.5 / 1 = 1.5$$

Matches expected value.

No contradiction exists.

Return false.

Example 2

Input:

equations = [["le","et"],["le","code"],["code","et"]]
values = [2,5,0.5]

Processing `le / et = 2`

Union components.

Processing `le / code = 5`

Now we derive:

$$code / et = 2/5 = 0.4$$

Processing `code / et = 0.5`

Both variables already belong to the same component.

Computed ratio:

$$0.4$$

Expected ratio:

$$0.5$$

Difference exceeds 1e-5.

Return true.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n α(n))	Union-Find operations are nearly constant time
Space	O(n)	Parent and weight maps store all variables

The inverse Ackermann function, denoted by $\alpha(n)$, grows extremely slowly and is effectively constant for all practical input sizes.

Each equation performs a small number of Union-Find operations, and path compression ensures the trees remain shallow.

Test Cases

sol = Solution()

# Example 1, consistent equations
assert sol.checkContradictions(
    [["a", "b"], ["b", "c"], ["a", "c"]],
    [3.0, 0.5, 1.5]
) is False

# Example 2, contradiction exists
assert sol.checkContradictions(
    [["le", "et"], ["le", "code"], ["code", "et"]],
    [2.0, 5.0, 0.5]
) is True

# Single equation, always valid
assert sol.checkContradictions(
    [["x", "y"]],
    [4.0]
) is False

# Direct contradiction
assert sol.checkContradictions(
    [["a", "b"], ["a", "b"]],
    [2.0, 3.0]
) is True

# Same equation repeated consistently
assert sol.checkContradictions(
    [["a", "b"], ["a", "b"]],
    [2.0, 2.0]
) is False

# Longer chain without contradiction
assert sol.checkContradictions(
    [["a", "b"], ["b", "c"], ["c", "d"], ["a", "d"]],
    [2.0, 3.0, 4.0, 24.0]
) is False

# Longer chain with contradiction
assert sol.checkContradictions(
    [["a", "b"], ["b", "c"], ["c", "d"], ["a", "d"]],
    [2.0, 3.0, 4.0, 25.0]
) is True

# Disconnected components
assert sol.checkContradictions(
    [["a", "b"], ["x", "y"]],
    [2.0, 3.0]
) is False

# Precision tolerance case
assert sol.checkContradictions(
    [["a", "b"], ["b", "c"], ["a", "c"]],
    [2.0, 3.0, 6.0000001]
) is False

# Contradiction caused by precision exceeding tolerance
assert sol.checkContradictions(
    [["a", "b"], ["b", "c"], ["a", "c"]],
    [2.0, 3.0, 6.1]
) is True

Test	Why
Simple consistent chain	Validates normal operation
Simple contradiction	Validates mismatch detection
Single equation	Smallest valid input
Duplicate inconsistent equation	Ensures contradictions are detected
Duplicate consistent equation	Ensures repeated equations are accepted
Long consistent chain	Tests transitive multiplication
Long inconsistent chain	Tests indirect contradiction
Disconnected graph	Ensures separate components work correctly
Precision tolerance	Verifies floating point handling
Large precision mismatch	Verifies contradiction threshold

Edge Cases

One important edge case occurs when two variables have never been seen before. A buggy implementation might attempt to access parent or weight information before initialization, causing errors or incorrect ratios. This solution handles that by lazily initializing every variable the first time it appears.

Another critical edge case is repeated equations between already connected variables. For example:

$$a / b = 2$$

followed later by:

$$a / b = 3$$

A naive Union-Find implementation that blindly merges sets would miss the contradiction. This implementation explicitly checks implied ratios whenever two variables already share the same root.

Floating point precision is also a common source of bugs. Multiplying many decimal ratios can introduce small numerical inaccuracies. Direct equality comparison would therefore be unreliable. The problem explicitly instructs us to compare using an epsilon threshold of 1e-5, which the implementation follows carefully.

A final important edge case involves long transitive chains. Consider:

$$a / b = 2,\ b / c = 3,\ c / d = 4$$

The algorithm must correctly infer:

$$a / d = 24$$

The weighted Union-Find structure maintains these relationships efficiently through accumulated weights and path compression.

LeetCode 2307 - Check for Contradictions in Equations

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Approach, Weighted Union-Find

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Processing a / b = 3

Processing b / c = 0.5

Processing a / c = 1.5

Example 2

Processing le / et = 2

Processing le / code = 5

Processing code / et = 0.5

Complexity Analysis

Test Cases

Edge Cases

Processing `a / b = 3`

Processing `b / c = 0.5`

Processing `a / c = 1.5`

Processing `le / et = 2`

Processing `le / code = 5`

Processing `code / et = 0.5`