Satisfiability of Equality Equations

TIP103 Unit 7 Session 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 25-30 mins
• 🛠️ Topics: Graphs, Union-Find (Disjoint Set), Connected Components

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What do the equations look like?

  • Each equation is exactly 4 characters: a single-letter variable, then "==" or "!=", then another single-letter variable, e.g. "a==b" or "a!=c".

• What does it mean for the equations to be satisfiable?

  • There must exist some assignment of integer values to the variables so that every equation holds at the same time. Equality is transitive: if a == b and b == c, then a must equal c.

• Can the same pair of variables appear in multiple equations?

  • Yes. For example, "a==b" and "b!=a" can both appear, and together they are contradictory, so the answer would be False.

HAPPY CASE
Input: equations = ["a==b", "b==c", "a==c"]
Output: True
Explanation: Assign a = b = c = 1. All three equations hold, so the equations are satisfiable.

Input: equations = ["a==b", "b!=c", "c==a"]
Output: False
Explanation: "a==b" and "c==a" force a, b, and c to share one value, but "b!=c" demands b and c differ. Contradiction.

EDGE CASE
Input: equations = ["a==b", "b!=a"]
Output: False
Explanation: The same pair is required to be both equal and unequal, which is impossible.

Input: equations = ["a!=a"]
Output: False
Explanation: A variable can never be unequal to itself, so this single equation is unsatisfiable.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Grouping Elements by Connectivity, we can consider the following approaches:

• Union-Find (Disjoint Set): Treat each "==" equation as an edge merging two variables into the same group, then check every "!=" equation for a contradiction.
• DFS on a Graph: Build a graph from the "==" edges and use DFS to label connected components, then verify the "!=" equations across components.

The two-pass Union-Find approach is the most natural fit: equality is an equivalence relation, and disjoint sets model equivalence classes directly.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Process the equations in two passes. In the first pass, union the two variables of every "==" equation so that all variables forced to be equal end up in the same disjoint set. In the second pass, examine every "!=" equation: if its two variables have the same root, they were forced equal by the "==" equations, which contradicts the inequality, so return False. If no "!=" equation is violated, return True — assigning each set its own distinct integer satisfies everything.

1) Create a `parent` map for the Union-Find structure.
2) Define find(x):
   a) If x is unseen, make it its own parent.
   b) Follow parent pointers to the root, compressing the path along the way.
3) Define union(x, y): set the root of x's tree to point at the root of y's tree.
4) PASS 1: For each equation of the form "x==y", call union(x, y).
5) PASS 2: For each equation of the form "x!=y", if find(x) == find(y), return False.
6) Return True.

⚠️ Common Mistakes

• Processing equations in a single pass in input order, so an "!=" check runs before a later "==" merges its variables (e.g. ["a!=b", "b==a"] would be wrongly accepted).
• Forgetting the self-inequality case: "x!=x" must return False, which the root comparison handles automatically since find(x) == find(x).
• Parsing the operator from the wrong index — the operator's first character is at index 1, and the second variable is at index 3, not index 2.

4: I-mplement

Implement the code to solve the algorithm.

def equations_possible(equations):
    parent = {}

    def find(x):
        # Initialize each new variable as its own root
        if x not in parent:
            parent[x] = x
        # Path compression: walk up to the root, flattening as we go
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

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

    # Pass 1: union all variables joined by "=="
    for eq in equations:
        if eq[1] == '=':
            union(eq[0], eq[3])

    # Pass 2: any "!=" between variables in the same group is a contradiction
    for eq in equations:
        if eq[1] == '!':
            if find(eq[0]) == find(eq[3]):
                return False

    return True

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: equations = ["a==b", "b!=a"]

  • Pass 1: union(a, b) puts a and b in the same set.
  • Pass 2: for "b!=a", find(b) == find(a), a contradiction.
  • Output: False

• Input: equations = ["a==b", "b==c", "a==c"]

  • Pass 1: union(a, b), union(b, c), union(a, c) — all three variables share one root.
  • Pass 2: no "!=" equations to check.
  • Output: True

• Input: equations = ["a==b", "b!=c", "c==a"]

  • Pass 1: union(a, b) and union(c, a) merge a, b, and c into one set.
  • Pass 2: for "b!=c", find(b) == find(c), a contradiction.
  • Output: False

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of equations. Since variables are single lowercase letters, there are at most 26 distinct variables.

• Time Complexity: O(N * α(26)), effectively O(N) — each of the two passes touches every equation once, and each find/union is near-constant time with path compression (α is the inverse Ackermann function).
• Space Complexity: O(1) — the parent map holds at most 26 entries regardless of N.