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 trueif there is a contradiction, orfalseotherwise.
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.
Input: equations =[["a","b"],["b","c"],["a","c"]], values =[3,0.5,1.5]Output: falseExplanation: The given equations are: a / b =3, b / c =0.5, a / c =1.5There are no contradictions in the equations. One possible assignment to satisfy all equations is:a =3, b =1 and c =2.
Example 2:
1
2
3
4
5
6
Input: equations =[["le","et"],["le","code"],["code","et"]], values =[2,5,0.5]Output: trueExplanation:
The given equations are: le / et =2, le / code =5, code / et =0.5Based on the first two equations, we get code / et =0.4.Since the third equation is code / et =0.5, we get a contradiction.
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:
Map each variable to an integer id.
Use union-find with a parent array and a weight array, where weight[i] is the ratio between i and its parent.
For each equation, union the two variables and check for contradiction.
When uniting, if the variables are already connected, check if the ratio matches (within 1e-5).
If a contradiction is found, return true. Otherwise, return false.
classSolution:
defcheckContradictions(self, equations: list[list[str]], values: list[float]) -> bool:
id = {}
n =0for a, b in equations:
if a notin id:
id[a] = n
n +=1if b notin id:
id[b] = n
n +=1 p = list(range(n))
w = [1.0] * n
deffind(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:
returnTrueelse:
p[px] = py
w[px] = w[y] * v / w[x]
returnFalse