medium

Satisfiability of Equality Equations

Determine whether a list of equality and inequality equations can all be satisfied.

1. Define the problem

Satisfiability of Equality Equations

You are given an array of strings equations that represent relationships between variables where each string equationsi is of length 4 and takes one of two forms: "xi==yi" or "xi!=yi". Return true if it is possible to assign integers to variable names so as to satisfy all the given equations, or false otherwise. Union every "==" pair first, then check every "!=" pair — if the two sides already share a root , the equations contradict each other.

Constraints

  • 1 ≤ equations.length ≤ 500
  • equationsi.length == 4
  • equationsi[0] and equationsi[3] are lowercase letters

Example

Inputequations = ["a==b","b!=a"]
Outputfalse

Explanation The first equation says a and b are equal, but the second says they are not — a contradiction.

2. Visualize the solution

Union all == pairs first, then check every != pair

Union all == pairs first, then check every != pair
Statusunion

"a==b": union a and b. They now share a root.

What happens in this step

union(a, b)
find(a) → a   find(b) → b
roots differ → union: parent[a] = b
parent: { a: a, b: b } → { a: b, b: b }

a and b are merged into one group, represented by root b.
Step 1 of 3

Steps to visualize

  1. Make one pass over the equations, unioning both sides of every "==" equation.
  2. Make a second pass over the equations, and for every "!=" equation compare find on both sides.
  3. If any "!=" pair already shares a root from the first pass, the equations are unsatisfiable.
  4. If no "!=" pair ever matches, every equation can be satisfied.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Union all == pairs first, then check every != pair
Statusunion

"a==b": union a and b. They now share a root.

What happens in this step

union(a, b)
find(a) → a   find(b) → b
roots differ → union: parent[a] = b
parent: { a: a, b: b } → { a: b, b: b }

a and b are merged into one group, represented by root b.
Step 1 of 3
4. Solution

Solution

solution.tsTypeScript
function equationsPossible(equations) {
  const parent = {};

  function ensure(x) {
    if (!(x in parent)) {
      parent[x] = x;
    }
  }

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

  function union(a, b) {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA !== rootB) {
      parent[rootA] = rootB;
    }
  }

  for (const eq of equations) {
    if (eq[1] === '=') {
      union(eq[0], eq[3]);
    }
  }

  for (const eq of equations) {
    if (eq[1] === '!') {
      if (find(eq[0]) === find(eq[3])) {
        return false;
      }
    }
  }

  return true;
}
Time
O(n · α(n))
Space
O(1) — at most 26 variables
5. Test cases

Test cases

InputExpectedCovers
equations = ["a==b","b!=a"]falseexample from the docstring
equations = ["b==a","a==b"]truethe same equality stated twice with sides swapped
equations = ["a==b","b==c","a==c"]truea chain of equalities with a consistent closing equation
equations = ["a==b","b!=c","c==a"]falsea contradiction only visible once all three variables are linked
equations = ["a==a"]truea variable declared equal to itself is always satisfiable
equations = ["a!=a"]falsea variable declared unequal to itself can never be satisfied
equations = ["a==b","c==d","a!=c"]truetwo separate equality groups with no shared variable stay consistent

Keep reading