Problem Description

You are given a list of equations representing relationships between variables. Each equation is of the form a == b or a != b, where a and b are variable names consisting of lowercase letters. Your task is to determine if it is possible to assign values to the variables such that all equations are satisfied.

Key constraints:

• Each equation is a string in the format "a==b" or "a!=b".
• There may be up to 500 equations.
• There is only one valid answer: either it is possible to satisfy all equations or it is not.
• Do not reuse or ignore any equation; all must be considered.

The function should return true if it is possible to satisfy all equations, and false otherwise.

Thought Process

At first glance, we might think to check every possible assignment of values to variables to see if all equations can be satisfied. However, with up to 500 equations and potentially 26 variables, this brute-force approach is computationally infeasible.

Instead, let's think in terms of relationships:

• Equations with == mean two variables must have the same value.
• Equations with != mean two variables must have different values.

This naturally leads us to use the Union-Find (Disjoint Set Union) data structure, which efficiently tracks which variables are in the same group.

Solution Approach

We'll use the Union-Find data structure to efficiently group variables that must be equal. The algorithm proceeds in two main steps:

1. Process all equality (==) equations:
   • For each equation a==b, merge the sets containing a and b. This means they must be equal.
2. Check all inequality (!=) equations:
   • For each equation a!=b, check if a and b are in the same set.
   • If they are, this is a contradiction, so return false.
   • If all inequalities are satisfied, return true.

Why Union-Find? Because it allows us to efficiently merge sets and check if two variables are in the same set, both in nearly constant time.

Implementation Details:

• We can map each variable (from 'a' to 'z') to an index (0 to 25).
• Parent array represents the root parent of each variable.
• We perform union operations for all == equations, then check for contradictions with != equations.

Example Walkthrough

Example Input: ["a==b", "b!=c", "c==a"]

1. Process equalities:
   • a==b: Union 'a' and 'b'. Now, 'a' and 'b' are in the same set.
   • c==a: Union 'c' and 'a'. Now, 'a', 'b', and 'c' are in the same set.
2. Check inequalities:
   • b!=c: Are 'b' and 'c' in the same set? Yes, because both are connected through 'a'.
   • This is a contradiction. Return false.

Another Example: ["a==b", "b!=c"]

• a==b: Union 'a' and 'b'.
• b!=c: 'b' and 'c' are not in the same set, so no contradiction. Return true.

Time and Space Complexity

• Brute-force approach:
  • Time: Exponential, since you would need to try all possible assignments of values to variables.
  • Space: Exponential, for storing all possible assignments.
• Optimized (Union-Find) approach:
  • Time: O(N * α(N)), where N is the number of equations and α(N) is the inverse Ackermann function (very small, nearly constant).
  • Space: O(1), since there are only 26 possible variables (a-z), so the parent array is size 26.

Summary

By modeling the problem as a set of equivalence classes, we can efficiently solve it using the Union-Find data structure. We first group variables that must be equal, then check for any contradictions among variables that must be unequal. This approach is both elegant and efficient, turning a seemingly complex logic problem into a matter of set management.

Code Implementation

class Solution:
    def equationsPossible(self, equations):
        parent = [i for i in range(26)]

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            parent[find(x)] = find(y)

        # First, process all '==' equations
        for eq in equations:
            if eq[1:3] == '==':
                a = ord(eq[0]) - ord('a')
                b = ord(eq[3]) - ord('a')
                union(a, b)

        # Then, process all '!=' equations
        for eq in equations:
            if eq[1:3] == '!=':
                a = ord(eq[0]) - ord('a')
                b = ord(eq[3]) - ord('a')
                if find(a) == find(b):
                    return False
        return True
      

class Solution {
public:
    int find(vector<int>& parent, int x) {
        if (parent[x] != x)
            parent[x] = find(parent, parent[x]);
        return parent[x];
    }
    void unite(vector<int>& parent, int x, int y) {
        parent[find(parent, x)] = find(parent, y);
    }
    bool equationsPossible(vector<string>& equations) {
        vector<int> parent(26);
        for (int i = 0; i < 26; ++i) parent[i] = i;
        // First, process all '==' equations
        for (string& eq : equations) {
            if (eq[1] == '=') {
                int a = eq[0] - 'a', b = eq[3] - 'a';
                unite(parent, a, b);
            }
        }
        // Then, process all '!=' equations
        for (string& eq : equations) {
            if (eq[1] == '!') {
                int a = eq[0] - 'a', b = eq[3] - 'a';
                if (find(parent, a) == find(parent, b))
                    return false;
            }
        }
        return true;
    }
};
      

class Solution {
    public boolean equationsPossible(String[] equations) {
        int[] parent = new int[26];
        for (int i = 0; i < 26; i++) parent[i] = i;

        for (String eq : equations) {
            if (eq.charAt(1) == '=') {
                int a = eq.charAt(0) - 'a';
                int b = eq.charAt(3) - 'a';
                union(parent, a, b);
            }
        }
        for (String eq : equations) {
            if (eq.charAt(1) == '!') {
                int a = eq.charAt(0) - 'a';
                int b = eq.charAt(3) - 'a';
                if (find(parent, a) == find(parent, b))
                    return false;
            }
        }
        return true;
    }

    private int find(int[] parent, int x) {
        if (parent[x] != x)
            parent[x] = find(parent, parent[x]);
        return parent[x];
    }

    private void union(int[] parent, int x, int y) {
        parent[find(parent, x)] = find(parent, y);
    }
}
      

var equationsPossible = function(equations) {
    const parent = new Array(26);
    for (let i = 0; i < 26; i++) parent[i] = i;

    function find(x) {
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    }

    function union(x, y) {
        parent[find(x)] = find(y);
    }

    // First, process all '==' equations
    for (let eq of equations) {
        if (eq[1] === '=') {
            const a = eq.charCodeAt(0) - 97;
            const b = eq.charCodeAt(3) - 97;
            union(a, b);
        }
    }
    // Then, process all '!=' equations
    for (let eq of equations) {
        if (eq[1] === '!') {
            const a = eq.charCodeAt(0) - 97;
            const b = eq.charCodeAt(3) - 97;
            if (find(a) === find(b)) return false;
        }
    }
    return true;
};