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, or false otherwise.
Note:
10-5.double is enough to solve the problem.
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 <= 100equations[i].length == 21 <= Ai.length, Bi.length <= 5Ai, Bi consist of lowercase English letters.equations.length == values.length0.0 < values[i] <= 10.0values[i] has a maximum of 2 decimal places.Problem Overview: You receive equations like a / b = value. The task is to determine whether the entire set of equations can coexist without conflict. If any equation implies a different ratio than what can already be derived from previous equations, a contradiction exists.
Approach 1: Graph Traversal with Ratio Propagation (DFS) (Time: O(E + V), Space: O(V + E))
Model each variable as a node in a graph. An equation a / b = k creates two directed edges: a → b with weight k and b → a with weight 1/k. When a new equation appears, run a depth-first search from a to see if b is already reachable. If reachable, multiply edge weights along the path to compute the implied ratio. If this computed ratio differs from the given value (beyond a small floating-point tolerance), the system contains a contradiction.
This approach explicitly explores relationships in the graph and checks consistency whenever a new equation is added. It works well when the graph is relatively small or when you want a clear visualization of dependencies between variables.
Approach 2: Weighted Union-Find (Disjoint Set with Ratios) (Time: O(n α(n)), Space: O(n))
The optimal solution uses Union-Find with weights. Each variable belongs to a set with a representative root. Along with the parent pointer, store a weight that represents the ratio between the node and its parent. Path compression keeps trees shallow while preserving ratio relationships.
When processing an equation a / b = k, find the roots of a and b. If the roots differ, union the sets while adjusting weights so that the ratio constraint holds across the merged structure. If both variables already share the same root, compute the implied ratio using stored weights. If the derived ratio does not match k, the equation contradicts earlier information.
This structure efficiently maintains multiplicative relationships between variables and quickly detects inconsistencies without re-traversing the graph. Each union or find operation runs in nearly constant time due to path compression and union by rank.
Recommended for interviews: Weighted Union-Find is the expected solution. The DFS graph approach shows you understand how equations form multiplicative paths, but it may re-traverse the graph repeatedly. Union-Find stores those relationships incrementally and detects contradictions in near O(n) time, which demonstrates stronger algorithmic design.
First, we convert the strings into integers starting from 0. Then, we traverse all the equations, map the two strings in each equation to the corresponding integers a and b. If these two integers are not in the same set, we merge them into the same set and record the weights of the two integers, which is the ratio of a to b. If these two integers are in the same set, we check whether their weights satisfy the equation. If not, we return true.
The time complexity is O(n times log n) or O(n times \alpha(n)), and the space complexity is O(n). Here, n is the number of equations.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph Traversal (DFS Ratio Check) | O(E + V) per traversal | O(V + E) | Useful for understanding equation relationships or when the graph is small |
| Weighted Union-Find | O(n α(n)) | O(n) | Best general solution; quickly maintains ratios and detects contradictions |
Leetcode 2307. Check for Contradictions in Equations - bfs/dfs traversal method • Code-Yao • 527 views views
Watch 3 more video solutions →Practice Check for Contradictions in Equations with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor