2307. Check for Contradictions in Equations


Problem Description

You are given two pieces of data:

  1. A 2D array named equations, where the inner array consists of two strings [A, B].
  2. 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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which algorithm should you use to find a node that is close to the root of the tree?

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:

  1. 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.

  2. Initialize Parent and Weight Arrays: Two arrays are created:

    • p: An array where p[i] represents the parent of element i in the Union-Find tree structure.
    • w: A weight array where w[i] represents the weight of element i.
  3. Union-Find with Weighting:

    • The find function is implemented to recursively find the root parent of any given element x, 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 value v is encountered, the corresponding integer identifiers for A and B are found using the dictionary d. The root parents pa and pb of A and B are found using the find function.
    • If A and B are not already connected (i.e., do not have the same root parent), they are connected by setting the parent of pb to pa and updating the weight of pb to reflect the ratio of A to B as given by the new equation.
  4. Check for Contradictions:

    • If A and B are already connected, meaning they are in the same set, the algorithm checks if the weight relationship of A and B given by the current equation matches the one known by the structure. If they do not match within an epsilon (eps) range of 10^-5, it indicates a contradiction.
  5. Complexity Analysis:

    • The overall time complexity of the algorithm is O(n * alpha(n)) or O(n * log n) at worst, where n is the number of equations and alpha(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), where n 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.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Example 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:

  1. 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
  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.
  3. Union-Find with Weighting:

    • For the equation A / B = 2.0, we map "A" to 0 and "B" to 1. Since they are not currently in the same set, we connect them by setting p[1] to 0 and updating w[1] to 2.0.
    • Next, we have B / C = 3.0. "B" has been mapped to 1 and "C" to 2. Now, their sets are united, and we update p[2] to 1 (the parent of "B"), and w[2] is updated to 3.0.
    • Finally, we examine A / C = 6.0. "A" is 0 and "C" is 2. We notice that "A" and "C" are already indirectly connected through "B": A / B = 2.0 and B / C = 3.0, so we can infer that A / C should be 2.0 * 3.0 = 6.0. The observed and inferred ratios match, so there's no contradiction.
  4. 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.

  5. 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)) or O(n * log n) at worst applies, ensuring efficiency. The space complexity remains O(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
Not Sure What to Study? Take the 2-min Quiz:

How does quick sort divide the problem into subproblems?

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:

  1. The construction of the mapping d from variables to their representative indices and the initial setups for p (parent array) and w (weight array) take O(N) time, where N is the number of unique variables in the equations.

  2. The iteration over the equations and values (for (a, b), v in zip(equations, values):). There could be up to E equations. The find-union algorithm typically has a near-constant time complexity under path compression and union-by-rank or size heuristics, often considered O(α(N)), where α is the inverse Ackermann function, which is very slow-growing and for all practical purposes can be considered as O(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:

  1. The map d, with a size proportional to the number of unique elements N.
  2. The parent array p and the weight array w, both of which have N 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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫