Satisfiability of Equality Equations

Share

Determine if a list of equations (like "a==b", "b!=c") can all be satisfied simultaneously.

Example 1
Input: equations=["a==b","b!=c","c==a"] → Output: false
Example 2
Input: equations=["c==c","b==d","x!=z"] → Output: true

Solution Approach

Two passes: first union all "==" pairs; then check "!=" pairs for conflicts.

  • First pass: union all a==b pairs
  • Second pass: for each a!=b pair: if find(a)==find(b) return false (contradiction)
  • Return true if no contradictions
Java
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) == '=')
            parent[find(parent, eq.charAt(0)-'a')] = find(parent, eq.charAt(3)-'a');
    for (String eq : equations)
        if (eq.charAt(1) == '!' && find(parent, eq.charAt(0)-'a') == find(parent, eq.charAt(3)-'a'))
            return false;
    return true;
}
private int find(int[] parent, int x) {
    return parent[x] == x ? x : (parent[x] = find(parent, parent[x]));
}
  • Time Complexity: O(n * alpha(26))
  • Space Complexity: O(1)