2307. Check for Contradictions in Equations
Problem Description
You are given two pieces of data:
- A 2D array named
equations
, where the inner array consists of two strings[A, B]
. - An array of real numbers called
values
.
For each small array in equations
, such as [A_i, B_i]
, the associated number in values
represents the ratio of the first string to the second (i.e., A_i / B_i = values[i]
).
The challenge is to determine if any of the provided equations contradict each other. A contradiction will arise if you have two equations that imply different ratios for the same pair of strings. For instance, if the equations say A / B = 2
and B / A = 0.3
, you have a contradiction because if A
is twice B
, then B
cannot be three times more than A
.
You should return true
if a contradiction is found, or false
otherwise. When comparing two numbers for equality, you'll consider them equal if they differ by less than a tiny amount (10^-5
). Precision shouldn't be an issue as using double
for calculations is sufficient according to the problem statement.
Flowchart Walkthrough
Let's analyze the problem in LeetCode 2307. Check for Contradictions in Equations using the algorithm flowchart provided here: Algorithm Flowchart. We will follow the flowchart steps to identify the suitable algorithm:
Is it a graph?
- Yes: The equations can form a graph where each variable is a node, and each equality or inequality creates edges with or without constraints.
Is it a tree?
- No: The graph can contain cycles, especially due to the presence of contradictions, hence it's not a tree.
Is the problem related to directed acyclic graphs (DAGs)?
- Yes: The nature of equations suggests that there should ideally be a consistent direction (from lesser value to greater value), mimicking a directed acyclic graph when there are no contradictions.
Is it related to topological sorting?
- Yes: Establishing a consistent ordering of the variables in a manner that adheres to the inequality and equality constraints could conceptually utilize topological sorting.
Conclusion: Using Depth-First Search to perform a topological sort checks the graph for the existence of directed cycles, which indicate contradictions in the equations, thus making DFS an appropriate choice for this problem.
Intuition
To solve this problem, we need to keep track of the known ratios in a way that allows us to efficiently update and check for contradictions. A good strategy for this problem is the Union-Find algorithm, also known as Disjoint Set Union (DSU), which is commonly used for problems involving the partitioning of elements into disjoint sets and checking for set inclusion quickly.
The intuition for using Union-Find with weighting comes from the idea that each string can be represented by an integer, and the relationship or 'ratio' between any two strings is the 'weight'. So when two strings that have been identified by integers are not already part of the same set (i.e., do not have a known relationship), we can merge their sets and establish the relationship by recording the weight.
However, when we encounter a pair that is already part of the same set, we already have an inferred ratio between them. If this inferred ratio doesn't match the one given in the current equation, we identify this as a contradiction.
The Union-Find structure not only helps in finding and merging sets but also in compressing paths which makes subsequent searches faster. All of these operations together will result in a solution that is efficient both in terms of time and space.
Learn more about Depth-First Search, Union Find and Graph patterns.
Solution Approach
The solution makes use of the Union-Find data structure, which is an efficient data structure that keeps track of elements split into one or more disjoint sets. Its primary operations are to find which set a particular element is in, and to unify two sets. The solution uses a weighted Union-Find, which means that each 'union' operation also considers the weight or ratio between the elements.
Here is a step-by-step breakdown of the algorithm used in the solution:
-
Map Strings to Integers: To implement the Union-Find data structure, we first map each unique string in the
equations
array to a unique integer identifier. This step is necessary because Union-Find typically operates on integer arrays. -
Initialize Parent and Weight Arrays: Two arrays are created:
p
: An array wherep[i]
represents the parent of elementi
in the Union-Find tree structure.w
: A weight array wherew[i]
represents the weight of elementi
.
-
Union-Find with Weighting:
- The
find
function is implemented to recursively find the root parent of any given elementx
, and during the find process, it also updates the weight of the elements along the path to reflect the ratio to the root. - When a new equation
(A, B)
with the valuev
is encountered, the corresponding integer identifiers forA
andB
are found using the dictionaryd
. The root parentspa
andpb
ofA
andB
are found using thefind
function. - If
A
andB
are not already connected (i.e., do not have the same root parent), they are connected by setting the parent ofpb
topa
and updating the weight ofpb
to reflect the ratio ofA
toB
as given by the new equation.
- The
-
Check for Contradictions:
- If
A
andB
are already connected, meaning they are in the same set, the algorithm checks if the weight relationship ofA
andB
given by the current equation matches the one known by the structure. If they do not match within an epsilon (eps
) range of10^-5
, it indicates a contradiction.
- If
-
Complexity Analysis:
- The overall time complexity of the algorithm is
O(n * alpha(n))
orO(n * log n)
at worst, wheren
is the number of equations andalpha(n)
is the inverse Ackermann function, which grows extremely slowly and for all practical input sizes behaves almost like a constant, making Union-Find operations highly efficient. - The space complexity is
O(n)
, wheren
is the number of equations, as it uses additional arrays and a dictionary to map strings to integers and keep track of sets and their weights.
- The overall time complexity of the algorithm is
In conclusion, the application of the Union-Find data structure with the added aspect of weights enables the efficient detection of contradictions in a series of ratio equations among different entities.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach described above. Suppose you are given the following data:
1equations = [["A", "B"], ["B", "C"], ["A", "C"]] 2values = [2.0, 3.0, 6.0]
This means we have three equations:
1A / B = 2.0 2B / C = 3.0 3A / C = 6.0
Now, let's use the provided solution approach to check for contradictions:
-
Map Strings to Integers: We identify all unique strings in
equations
which are "A", "B", and "C". We then map them to integers for the elements of our Union-Find structure. Let's say we map them as follows:1"A" -> 0 2"B" -> 1 3"C" -> 2
-
Initialize Parent and Weight Arrays: We initialize two arrays of size
3
(since we have three unique strings):p = [0, 1, 2]
: Initially, each element is the parent of itself.w = [1.0, 1.0, 1.0]
: Initially, the weight of each element to itself is 1.
-
Union-Find with Weighting:
- For the equation
A / B = 2.0
, we map "A" to0
and "B" to1
. Since they are not currently in the same set, we connect them by settingp[1]
to0
and updatingw[1]
to2.0
. - Next, we have
B / C = 3.0
. "B" has been mapped to1
and "C" to2
. Now, their sets are united, and we updatep[2]
to1
(the parent of "B"), andw[2]
is updated to3.0
. - Finally, we examine
A / C = 6.0
. "A" is0
and "C" is2
. We notice that "A" and "C" are already indirectly connected through "B":A / B = 2.0
andB / C = 3.0
, so we can infer thatA / C
should be2.0 * 3.0 = 6.0
. The observed and inferred ratios match, so there's no contradiction.
- For the equation
-
Check for Contradictions: Since the calculated weights all align with the supplied values, we do not find any contradictions in this particular example. Therefore, the algorithm would return
false
indicating that there are no contradictions. -
Complexity Analysis: This example has run in near-constant time due to the small size and straightforward nature. For larger sets of equations, however, the time complexity of
O(n * alpha(n))
orO(n * log n)
at worst applies, ensuring efficiency. The space complexity remainsO(n)
as additional structures are used proportional to the number of unique elements (i.e., unique strings).
This example successfully demonstrates the effectiveness of the weighted Union-Find algorithm in identifying contradictions within a system of ratio equations.
Solution Implementation
1from typing import List
2from collections import defaultdict
3
4class Solution:
5 def checkContradictions(self, equations: List[List[str]], values: List[float]) -> bool:
6 # Helper function to find the root of an element using path compression.
7 def find_root(variable: int) -> int:
8 if parents[variable] != variable:
9 # Recursively find the root of the group.
10 root = find_root(parents[variable])
11 # Apply path compression and update the weight.
12 weights[variable] *= weights[parents[variable]]
13 parents[variable] = root
14 return parents[variable]
15
16 # Dictionary to map each distinct variable to an integer.
17 variable_to_index = defaultdict(int)
18 num_variables = 0
19 # Assign an index to every unique variable.
20 for equation in equations:
21 for var in equation:
22 if var not in variable_to_index:
23 variable_to_index[var] = num_variables
24 num_variables += 1
25
26 # Initialize parent pointers and weights for union-find structure.
27 parents = list(range(num_variables))
28 weights = [1.0] * num_variables
29
30 # Threshold for floating point comparison.
31 eps = 1e-5
32
33 # Process each equation along with its associated value.
34 for (var1, var2), value in zip(equations, values):
35 index1, index2 = variable_to_index[var1], variable_to_index[var2]
36 root1, root2 = find_root(index1), find_root(index2)
37
38 # If the two variables have different roots, they can be connected without causing a contradiction.
39 if root1 != root2:
40 parents[root2] = root1
41 weights[root2] = value * weights[index1] / weights[index2]
42 # If they belong to the same group, check for contradictions.
43 elif abs(value * weights[index1] - weights[index2]) >= eps:
44 return True
45
46 # No contradictions were found.
47 return False
48
1import java.util.*;
2
3class Solution {
4 private int[] parent; // Union-find parent array
5 private double[] weight; // Weight array to store the multiplication factor
6
7 // Method to check for contradictions in a list of equations with their values
8 public boolean checkContradictions(List<List<String>> equations, double[] values) {
9 Map<String, Integer> dictionary = new HashMap<>(); // Map for variable to index
10 int variableCount = 0; // Counter for the number of distinct variables
11 // Map each variable to an integer
12 for (List<String> equation : equations) {
13 for (String variable : equation) {
14 if (!dictionary.containsKey(variable)) {
15 dictionary.put(variable, variableCount++);
16 }
17 }
18 }
19
20 // Initialize the union-find structure
21 parent = new int[variableCount];
22 weight = new double[variableCount];
23 Arrays.fill(weight, 1.0); // Initialize all weights to 1
24 for (int i = 0; i < variableCount; ++i) {
25 parent[i] = i; // Initially, each element is its own parent
26 }
27
28 // Tolerance for floating-point comparison
29 final double EPSILON = 1e-5;
30
31 for (int i = 0; i < equations.size(); ++i) {
32 int indexA = dictionary.get(equations.get(i).get(0));
33 int indexB = dictionary.get(equations.get(i).get(1));
34
35 int parentA = find(indexA); // Find the parent of A
36 int parentB = find(indexB); // Find the parent of B
37 double value = values[i]; // Multiplication value for this equation
38
39 if (parentA != parentB) { // If they are not already in the same set
40 // Union the sets and update weights
41 parent[parentB] = parentA;
42 weight[parentB] = value * weight[indexA] / weight[indexB];
43 } else {
44 // Check for contradiction by comparing the actual value with the calculated one
45 if (Math.abs(value * weight[indexA] - weight[indexB]) >= EPSILON) {
46 return true; // There's a contradiction if the difference is greater than EPSILON
47 }
48 }
49 }
50 return false; // No contradictions found
51 }
52
53 // Union-find 'find' operation with path compression
54 private int find(int x) {
55 if (parent[x] != x) {
56 int root = find(parent[x]); // Recursively find the root
57 weight[x] *= weight[parent[x]]; // Update the weight of x
58 parent[x] = root; // Path compression: Point x directly to the root
59 }
60 return parent[x]; // Return the parent of x
61 }
62}
63
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <numeric> // for std::iota
5#include <cmath> // for std::fabs
6#include <functional> // for std::function
7
8class Solution {
9public:
10 // Main function to check contradictions within the equations
11 bool checkContradictions(std::vector<std::vector<std::string>>& equations, std::vector<double>& values) {
12 std::unordered_map<std::string, int> labelToIndexMap; // Maps each unique label to an integer index
13 int numLabels = 0; // Counter for unique labels in equations
14
15 // Assign each unique label an index
16 for (auto& equation : equations) {
17 for (auto& label : equation) {
18 if (!labelToIndexMap.count(label)) {
19 labelToIndexMap[label] = numLabels++;
20 }
21 }
22 }
23
24 // Parent array for Union-Find structure
25 std::vector<int> parent(numLabels);
26 // Initialize parents to be themselves (i.e., each element is its own parent)
27 std::iota(parent.begin(), parent.end(), 0);
28
29 // Weight array to keep track of relative weights of nodes in Union-Find
30 std::vector<double> weight(numLabels, 1.0);
31
32 // Function to find the root of a node and perform path compression
33 std::function<int(int)> findRoot = [&](int node) -> int {
34 if (parent[node] != node) {
35 int root = findRoot(parent[node]);
36 weight[node] *= weight[parent[node]];
37 parent[node] = root;
38 }
39 return parent[node];
40 };
41
42 // Iterating through each equation to perform union operations
43 for (int i = 0; i < equations.size(); ++i) {
44 int indexA = labelToIndexMap[equations[i][0]];
45 int indexB = labelToIndexMap[equations[i][1]];
46 double value = values[i]; // The relative weight value between A and B
47
48 int parentA = findRoot(indexA);
49 int parentB = findRoot(indexB);
50
51 // Union operation
52 if (parentA != parentB) {
53 // Linking parentB to parentA
54 parent[parentB] = parentA;
55 // Updating the weight of B's tree relative to A's
56 weight[parentB] = value * weight[indexA] / weight[indexB];
57 } else if (std::fabs(value * weight[indexA] - weight[indexB]) >= 1e-5) {
58 // If the parents are the same but the values are different (by a small threshold),
59 // then there is a contradiction.
60 return true;
61 }
62 }
63 // No contradictions were found
64 return false;
65 }
66};
67
1function checkContradictions(equations: string[][], values: number[]): boolean {
2 // Create a dictionary to map each string to a unique integer
3 const stringToIndex: { [key: string]: number } = {};
4 let nodeCount = 0; // Counter to assign unique integers
5
6 // Assign a unique integer to each unique string in the equations
7 for (const equation of equations) {
8 for (const element of equation) {
9 if (!(element in stringToIndex)) {
10 stringToIndex[element] = nodeCount++;
11 }
12 }
13 }
14
15 // Array to represent parents in the disjoint set
16 const parents: number[] = Array.from({ length: nodeCount }, (_, index) => index);
17
18 // Array to represent weights for each node, initializing as 1.0
19 const weights: number[] = new Array(nodeCount).fill(1.0);
20
21 // find function performs path compression and updates the weights
22 const find = (node: number): number => {
23 if (parents[node] !== node) {
24 const root = find(parents[node]);
25 weights[node] *= weights[parents[node]];
26 parents[node] = root;
27 }
28 return parents[node];
29 };
30
31 // Iterate through each equation
32 for (let i = 0; i < equations.length; i++) {
33 const indexA = stringToIndex[equations[i][0]];
34 const indexB = stringToIndex[equations[i][1]];
35 const value = values[i];
36
37 const parentA = find(indexA);
38 const parentB = find(indexB);
39
40 // If the two elements have different parents, join them
41 if (parentA !== parentB) {
42 parents[parentB] = parentA;
43 weights[parentB] = (value * weights[indexA]) / weights[indexB];
44 } else {
45 // If the two elements are already connected, check for contradictions
46 if (Math.abs(value * weights[indexA] - weights[indexB]) >= 1e-5) {
47 return true; // A contradiction is found
48 }
49 }
50 }
51
52 // If no contradictions were found
53 return false;
54}
55
Time and Space Complexity
Time Complexity
The primary operations in this algorithm are the find-union operations and the iteration over the list of equations. There are essentially two significant portions contributing to the time complexity:
-
The construction of the mapping
d
from variables to their representative indices and the initial setups forp
(parent array) andw
(weight array) takeO(N)
time, whereN
is the number of unique variables in the equations. -
The iteration over the equations and values (
for (a, b), v in zip(equations, values):
). There could be up toE
equations. The find-union algorithm typically has a near-constant time complexity under path compression and union-by-rank or size heuristics, often consideredO(α(N))
, whereα
is the inverse Ackermann function, which is very slow-growing and for all practical purposes can be considered asO(1)
.
On iteration of each equation, we are performing the find
operation two times and potentially a union
once which would still be within O(1)
due to path compression and heuristics. Since we are iterating over E
equations, our complexity for this part is O(E)
.
Therefore, the overall time complexity of the code can be expressed as O(N + E)
. However, simplifying further, since every variable appears at least once in the list of equations (implying E >= N/2
), it can be further simplified to O(E)
.
Space Complexity
The space complexity of the algorithm includes storage for:
- The map
d
, with a size proportional to the number of unique elementsN
. - The parent array
p
and the weight arrayw
, both of which haveN
elements.
So, the overall space complexity is O(N)
. However, since N
is bound by E
due to the fact every variable appears in the equations, we can similarly consider overall space complexity to be O(E)
.
Learn more about how to find time and space complexity quickly using problem constraints.
How does quick sort divide the problem into subproblems?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could