Solution Explanation: Weighted Union-Find

This problem can be efficiently solved using a weighted union-find algorithm. The core idea is to represent the equations as a graph where nodes are variables (letters) and edges represent the relationships between them (ratios). We then use union-find to check for inconsistencies in these relationships.

Algorithm:

1. Initialization:

   • Create a mapping from each variable (string) to a unique integer ID. This simplifies the representation within the union-find data structure.
   • Initialize a parent array p for union-find, where p[i] initially points to i (each node is its own parent). This indicates that each variable is initially in its own disjoint set.
   • Initialize a weight array w, where w[i] represents the weight or ratio associated with variable i. We initialize all weights to 1.0.

2. Iterate through Equations:

   • For each equation [A, B] with value v, perform the following:
     • Get the integer IDs a and b for variables A and B.
     • Find the root parent nodes for a and b using the find function (described below).
     • Union: If the roots (pa and pb) are different, it means the variables belong to different sets. We merge them by setting p[pb] = pa. We also update the weight w[pb] to reflect the relationship between the newly connected sets: w[pb] = v * w[a] / w[b].
     • Contradiction Check: If the roots are the same (pa == pb), it means the variables are already in the same set. We check for a contradiction by comparing v * w[a] with w[b]. If their absolute difference is greater than a small epsilon (e.g., 1e-5), it means there's a contradiction, and we return true.

3. Find Function (Path Compression):

   • The find function recursively finds the root parent of a node. Crucially, it performs path compression, which optimizes future find calls by updating the parent pointers along the path to the root, making subsequent lookups faster.

4. Return Result:

   • If no contradictions are found after processing all equations, we return false.

Time and Space Complexity:

• Time Complexity: The dominant operation is the union-find with path compression. The amortized time complexity of union-find with path compression is effectively O(α(n)), where α(n) is the inverse Ackermann function, which grows extremely slowly and is practically considered a constant. Therefore, the overall time complexity is O(n), where n is the number of equations.

• Space Complexity: The space complexity is O(n) due to the parent array p, weight array w, and the dictionary d to map strings to integers.

Code Examples (Python):

from collections import defaultdict
 
class Solution:
    def checkContradictions(self, equations: List[List[str]], values: List[float]) -> bool:
        d = defaultdict(int)  # Map strings to integer IDs
        n = 0
        for e in equations:
            for s in e:
                if s not in d:
                    d[s] = n
                    n += 1
 
        p = list(range(n))  # Parent array for union-find
        w = [1.0] * n      # Weight array
 
        def find(x: int) -> int:
            if p[x] != x:
                root = find(p[x])
                w[x] *= w[p[x]]  # Update weight during path compression
                p[x] = root
            return p[x]
 
        eps = 1e-5
        for (a, b), v in zip(equations, values):
            a, b = d[a], d[b]
            pa, pb = find(a), find(b)
            if pa != pb:
                p[pb] = pa
                w[pb] = v * w[a] / w[b]
            elif abs(v * w[a] - w[b]) >= eps:
                return True  # Contradiction found
        return False
 

The Java, C++, Go, and TypeScript implementations follow a very similar structure, with the appropriate data structure adaptations for each language. The core logic of the weighted union-find algorithm remains consistent.