Check for Contradictions in Equations - Video Solutions
Leetcode 2307. Check for Contradictions in Equations - bfs/dfs traversal method
Check for Contradictions in Equations - Video Solution
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 534 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- 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
doubleis 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,Biconsist of lowercase English letters.equations.length == values.length0.0 < values[i] <= 10.0values[i]has a maximum of 2 decimal places.
Approach Overview
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.
Complexity Analysis
| 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 |