Skip to main content
Talentd

Check for Contradictions in Equations - Solution & Explanation

HardPremiumFree on FleetCodeArrayDepth-First SearchUnion FindGraph9 min readAsked at: Amazon, Uber
Practice this problem

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 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 <= Ai.length, Bi.length <= 5
  • Ai, Bi consist of lowercase English letters.
  • equations.length == values.length
  • 0.0 < values[i] <= 10.0
  • values[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.

Solution

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:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Graph Traversal (DFS Ratio Check)O(E + V) per traversalO(V + E)Useful for understanding equation relationships or when the graph is small
Weighted Union-FindO(n α(n))O(n)Best general solution; quickly maintains ratios and detects contradictions

Video Solution

Leetcode 2307. Check for Contradictions in Equations - bfs/dfs traversal method • Code-Yao • 534 views views

Watch 3 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Check for Contradictions in Equations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Evaluate Division