Watch 4 video solutions for Check for Contradictions in Equations, a hard level problem involving Array, Depth-First Search, Union Find. This walkthrough by Code-Yao has 527 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |