Satisfiability of Equality Equations

Medium#990

You get equations of the form "p==q" or "p!=q", where p and q are lowercase letters standing for variables. Say whether the letters can be given values so that every equation holds. Our example: "a==b", "d!=b", "c!=a", "b==c" → false.

990 Satisfiability of Equality EquationsWalkthrough · 1×

Example: "a==b", "d!=b", "c!=a", "b==c". "c!=a" comes before "b==c": at that point c is still alone, and only the later equality ties c to a through b.

abcdaabbccddparentpass 1a==bd!=bc!=ab==c
looking at nowroot of a groupdone in this passan equality: nothing to check in pass 2the inequality that fails

Each letter is its own root: a, b, c, d. First pass: only the equalities

01/60
restart · back · play · step
Speed
1function equationsPossible(equations):
2 parent = {a: a, b: b, ..., z: z}
3 for (u, op, v) in equations:
4 if op is "==":
5 rootU = find(u)
6 rootV = find(v)
7 if rootU is not rootV:
8 parent[rootV] = rootU
9 for (u, op, v) in equations:
10 if op is "!=":
11 rootU = find(u)
12 rootV = find(v)
13 if rootU == rootV:
14 return false
15 return true
16
17function find(x):
18 while parent[x] is not x:
19 x = parent[x]
20 return x
state
parent
{a: a, b: b, c: c, d: d}
u
–
op
–
v
–
rootU
–
rootV
–
x
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Equal is catching: a == b and b == c make a == c. So the letters tied by equalities form groups, and every letter of a group has to get the same value.
  2. Different groups can always get different values, so the equations hold exactly when no inequality has both letters in one group, which is one comparison of roots.
  3. An inequality can be checked only once every equality is in: a later equality may still pull its letters into one group, as "b==c" does here.

Complexity

Time O(m · h) for m equations: two passes, two finds per equation, and a tree over at most 26 letters is at most 26 high, so this is O(m). Memory O(1): parent has one slot per letter of the alphabet.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.