Is Check for Contradictions in Equations easy or hard?

Check for Contradictions in Equations is classified as a Hard problem because it combines graph modeling with a weighted Union-Find structure. The challenge comes from maintaining multiplicative relationships during path compression and detecting inconsistencies when nodes already belong to the same component.

Check for Contradictions in Equations Python/Java solution

Implement a Weighted Union-Find where each variable maps to a parent and a ratio weight relative to that parent. The find operation applies path compression while updating weights. The union operation connects roots while maintaining the equation ratio constraint. This approach translates cleanly to Python, Java, C++, Go, and TypeScript.

How to solve Check for Contradictions in Equations in O(n)?

Use a weighted Union-Find structure that tracks ratios between nodes and their parents. For each equation a/b = k, find the roots of a and b and maintain the correct weight relationship during union. If both variables already share the same root, compute the implied ratio from stored weights and compare it with k to detect a contradiction. Path compression keeps operations nearly constant time.

What is the best approach for Check for Contradictions in Equations?

Weighted Union-Find (disjoint set with ratio weights) is the most efficient approach. It stores multiplicative relationships between variables while keeping sets compressed with path compression. Each equation either merges two components or verifies an existing relationship. This allows contradiction detection in near O(n) time.

Is Check for Contradictions in Equations asked at Google/Amazon/Meta?

Problems combining graph consistency checks and Union-Find appear frequently in interviews at large tech companies including Google, Amazon, and Meta. Variants often involve validating equations, evaluating divisions, or detecting conflicts in constraint systems. Interviewers expect candidates to recognize the Union-Find pattern.

What data structure is used in Check for Contradictions in Equations?

The core data structure is Weighted Union-Find (Disjoint Set Union). It maintains connected components of variables and stores ratio weights between nodes and their parents. Graph adjacency lists and DFS can also be used as an alternative modeling approach.

What is the time complexity of Check for Contradictions in Equations?

The optimal Weighted Union-Find solution runs in O(n α(n)) time, where α(n) is the inverse Ackermann function and behaves almost like a constant in practice. Each equation triggers a small number of find and union operations. Space complexity is O(n) to store parents, ranks, and ratio weights.

Description Hints 3 Solution Video 15:09

2307. Check for Contradictions in Equations

Hard43.8% acceptance2 companiesPremium elsewhere, free here

You are given a 2D array of strings equations and an array of real numbers values, where equations[i] = [A_i, B_i] and values[i] means that A_i / B_i = 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 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 <= 100
equations[i].length == 2
1 <= A_i.length, B_i.length <= 5
A_i, B_i consist of lowercase English letters.
equations.length == values.length
0.0 < values[i] <= 10.0
values[i] has a maximum of 2 decimal places.

Asked at 2 companies

Uber Amazon

Topics

Hints open one at a time

Hint 1

Try treating this as a graph problem.

Hint 2

Each variable is a node, and each equation is an edge.

Hint 3

Try performing DFS multiple times to find contradictions.

15:09

Still stuck?Read the written solution, or watch a walkthrough.

Open solution