Code Implementation

class Solution:
    def equationsPossible(self, equations):
        parent = {}

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

        # Step 1: Union for equalities
        for eq in equations:
            if eq[1:3] == "==":
                a, b = eq[0], eq[3]
                parent[find(a)] = find(b)

        # Step 2: Check inequalities
        for eq in equations:
            if eq[1:3] == "!=":
                a, b = eq[0], eq[3]
                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];
    }

    bool equationsPossible(vector<string>& equations) {
        vector<int> parent(26);
        for (int i = 0; i < 26; ++i) parent[i] = i;

        // Step 1: Union for equalities
        for (const string& eq : equations) {
            if (eq[1] == '=') {
                int a = eq[0] - 'a', b = eq[3] - 'a';
                parent[find(parent, a)] = find(parent, b);
            }
        }
        // Step 2: Check inequalities
        for (const 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;

        // Find with path compression
        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }

        // Step 1: Union for equalities
        for (String eq : equations) {
            if (eq.charAt(1) == '=') {
                int a = eq.charAt(0) - 'a', b = eq.charAt(3) - 'a';
                parent[find(a)] = find(b);
            }
        }
        // Step 2: Check inequalities
        for (String eq : equations) {
            if (eq.charAt(1) == '!') {
                int a = eq.charAt(0) - 'a', b = eq.charAt(3) - 'a';
                if (find(a) == find(b)) return false;
            }
        }
        return true;
    }

    // Helper method for find (since Java doesn't support nested functions)
    private int find(int[] parent, int x) {
        if (parent[x] != x) parent[x] = find(parent, parent[x]);
        return parent[x];
    }
}
      

var equationsPossible = function(equations) {
    const parent = {};
    const find = x => {
        if (!(x in parent)) parent[x] = x;
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    };

    // Step 1: Union for equalities
    for (let eq of equations) {
        if (eq[1] === '=') {
            parent[find(eq[0])] = find(eq[3]);
        }
    }
    // Step 2: Check inequalities
    for (let eq of equations) {
        if (eq[1] === '!') {
            if (find(eq[0]) === find(eq[3])) return false;
        }
    }
    return true;
};
      

Problem Description

Given an array of strings equations representing relationships between variables, each equation is of the form "a==b" or "a!=b", where a and b are lowercase English letters. Your task is to determine if it is possible to assign values to these variables such that all equations are satisfied at the same time.

• Each input equation is either an equality (==) or an inequality (!=).
• Variables are single lowercase letters ('a' to 'z').
• Return true if all equations can be satisfied, otherwise false.
• There may be multiple variables and equations, but only one valid assignment is required if possible.

Thought Process

At first glance, you might consider trying every possible assignment of values to variables, but with 26 possible variables, this quickly becomes infeasible. Instead, notice that equations like "a==b" group variables together, while "a!=b" separates them. This suggests a grouping or partitioning approach.

The key insight is to treat variables connected by equality as belonging to the same group or set. If two variables are in the same group, they must not be separated by an inequality. If any "a!=b" equation tries to separate variables in the same group, the system is unsatisfiable.

This leads us naturally to a data structure that can efficiently group and check membership: Union-Find (Disjoint Set Union).

Solution Approach

We use the Union-Find (Disjoint Set Union) data structure to efficiently group variables connected by equality and check for contradictions with inequalities.

1. Initialize parent pointers: For each variable, set its parent to itself. This means each variable starts in its own group.
2. Process all equality equations ("=="): For every equation like "a==b", merge the groups containing a and b. This ensures all variables that must be equal are grouped together.
3. Process all inequality equations ("!="): For every equation like "a!=b", check if a and b are in the same group. If they are, this is a contradiction and the answer is false.
4. If no contradictions are found: If all inequalities are satisfied (no variables in the same group are required to be different), return true.

Why Union-Find? Union-Find allows us to merge sets and check if two elements belong to the same set in nearly constant time, making it ideal for this problem.

Example Walkthrough

Consider the input: ["a==b", "b==c", "a!=c"]

1. Process equalities:
   • "a==b": Group a and b together. Now, a and b are in the same set.
   • "b==c": Group b and c. Now, a, b, and c are all in the same set.
2. Process inequalities:
   • "a!=c": Check if a and c are in the same set. They are, so this is a contradiction.
3. Therefore, the answer is false.

For a satisfiable example: ["a==b", "b!=c"]

• a and b are grouped together.
• b!=c: b and c are in different sets, so there is no contradiction.
• The answer is true.

Time and Space Complexity

Brute-force approach: Trying every possible assignment of values to 26 variables would be exponential time, which is infeasible.

Optimized (Union-Find) approach:

• Time Complexity: Each find and union operation takes nearly constant time (amortized O(α(N)), where α is the inverse Ackermann function, which grows extremely slowly). With up to 2N operations (N equations), the total time is effectively O(N).
• Space Complexity: We store up to 26 parent pointers (one per variable), so space is O(1).

Summary

The problem is elegantly solved by modeling variable relationships as groups using the Union-Find data structure. By first grouping variables that must be equal, and then checking inequalities for contradictions, we efficiently determine satisfiability. This approach is both fast and memory-efficient, and showcases the power of classic data structures for reasoning about equivalence relations.