What is the brute force approach and complexity for Satisfiability of Equality Equations?

BFS over the == links from one letter, once for each != with time complexity O(N · (26 + N)) and space complexity O(26 + N).

What is the optimal approach and complexity for Satisfiability of Equality Equations?

Union-Find: merge every == pair, then fail a != whose letters share a root with optimal time complexity O(N · α) and space complexity O(1).

How do you identify the pattern for Satisfiability of Equality Equations?

Look for key signals in the prompt: "x == y" indicates Joins x and y into one group. Equal is transitive, so the group grows along chains of `==`.; "x != y" indicates A rule to check against the finished groups, not something to union.; "can all the equations hold together" indicates One contradiction is enough to return false, and no contradiction means true..

Satisfiability of Equality Equations

Medium·LeetCode #990Basic Anchor

LeetCode

Jump:

30-Second Mental ModelUnion-Find (equivalence) — union every equality, then check the inequalities

Complexity:O(N · (26 + N))→O(N · α)

Key Insight

Keep one group per letter. Join every == pair first, then check each != against the finished groups. Two letters with the same root are linked by a chain of ==, so a != between them is a contradiction.

Core Validity Invariant

After every == is merged, two letters are forced equal exactly when they share a root, so a != between them is a contradiction.

Problem

You get a list of equations between single lowercase letters. Each equation is either x==y, which says x and y must be equal, or x!=y, which says they must be different.

Return true if you can give every letter a value so that all the equations hold at the same time. Return false if the equations contradict each other.

Input

equations: a list of 4-character strings. Each one is a letter, then == or !=, then a letter. For example "a==b".

Output

true if all equations can hold together, false otherwise.

Example 1

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

Output: false

a equals b, so b cannot be different from a.

Example 2

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

Output: true

Both equations say the same thing, so they agree.

Example 3

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

Output: false

a equals b and c equals a, so b equals c. That breaks b!=c.

Example 4

Input: equations = ["c==c", "b==d", "x!=z"]

Output: true

c equals itself, b and d are linked to each other only, and x and z are unrelated.

Constraints

• 1 <= equations.length <= 500
• equations[i].length == 4
• equations[i][0] is a lowercase letter
• equations[i][1] is either '=' or '!'
• equations[i][2] is '='
• equations[i][3] is a lowercase letter

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
An == links two letters together. Which letters end up linked once I follow every == I have?
2.
Suppose the list is a!=b, then a==c, then c==b. Can I decide a!=b the moment I read it? Why not?
3.
Which structure already keeps track of sets of linked items, and how do I ask whether two items are in the same set?
4.
Does a!=a need its own special case, or can the same check handle it?
5.
What do I need to know about the whole list before I can judge a single !=?

Brute force approach

Idea

Build a graph on the 26 letters with an edge for every ==. For each !=, run a search from one of its letters. If the other letter is reachable, a chain of == makes them equal, so that != is broken.

Thinking process

1
Each == is an edge. Two letters are forced equal exactly when a path of edges joins them.
2
Take a==b, b==c, c!=a. The graph has the edges a-b and b-c. Searching from c reaches b and then a, so c and a are equal through the chain, and c!=a is broken.
3
Each search touches at most 26 letters and at most N edges, so one != costs about O(26 + N) work.
4
a!=a needs no special case. The search starts at a, and a is always reached, so the function returns false.
5
The graph never changes, but the search is rebuilt for every !=. Repeating that work is what the optimal removes.

Code & Implementation

brute.cpp

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        // Graph on the 26 letters: each "==" is an edge both ways.
        vector<vector<int>> adj(26);
        for (auto& e : equations) {
            if (e[1] != '=') continue;
            int a = e[0] - 'a', b = e[3] - 'a';
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        // For each "!=", search from one letter. If the other letter is reachable,
        // a chain of "==" makes them equal, so the "!=" is broken.
        for (auto& e : equations) {
            if (e[1] != '!') continue;
            int from = e[0] - 'a', to = e[3] - 'a';
            vector<bool> seen(26, false);
            queue<int> q;
            q.push(from);
            seen[from] = true;
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                for (int v : adj[u])
                    if (!seen[v]) { seen[v] = true; q.push(v); }
            }
            if (seen[to]) return false;   // also catches a!=a: "from" is always seen
        }
        return true;
    }
};

import java.util.*;

class Solution {
    public boolean equationsPossible(String[] equations) {
        // Graph on the 26 letters: each "==" is an edge both ways.
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            adj.add(new ArrayList<>());
        }
        for (String e : equations) {
            if (e.charAt(1) != '=') continue;
            int a = e.charAt(0) - 'a', b = e.charAt(3) - 'a';
            adj.get(a).add(b);
            adj.get(b).add(a);
        }
        // For each "!=", search from one letter. If the other letter is reachable,
        // a chain of "==" makes them equal, so the "!=" is broken.
        for (String e : equations) {
            if (e.charAt(1) != '!') continue;
            int from = e.charAt(0) - 'a', to = e.charAt(3) - 'a';
            boolean[] seen = new boolean[26];
            Queue<Integer> q = new ArrayDeque<>();
            q.offer(from);
            seen[from] = true;
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : adj.get(u)) {
                    if (!seen[v]) {
                        seen[v] = true;
                        q.offer(v);
                    }
                }
            }
            if (seen[to]) return false;
        }
        return true;
    }
}

from typing import List
from collections import deque

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        # Graph on the 26 letters: each "==" is an edge both ways.
        adj: List[List[int]] = [[] for _ in range(26)]
        for e in equations:
            if e[1] != '=':
                continue
            a, b = ord(e[0]) - ord('a'), ord(e[3]) - ord('a')
            adj[a].append(b)
            adj[b].append(a)

        # For each "!=", search from one letter. If the other letter is reachable,
        # a chain of "==" makes them equal, so the "!=" is broken.
        for e in equations:
            if e[1] != '!':
                continue
            from_node, to_node = ord(e[0]) - ord('a'), ord(e[3]) - ord('a')
            seen = [False] * 26
            q = deque([from_node])
            seen[from_node] = True
            while q:
                u = q.popleft()
                for v in adj[u]:
                    if not seen[v]:
                        seen[v] = True
                        q.append(v)
            if seen[to_node]:
                return False
        return True

export function equationsPossible(equations: string[]): boolean {
    // Graph on the 26 letters: each "==" is an edge both ways.
    const adj: number[][] = Array.from({ length: 26 }, () => []);
    for (const e of equations) {
        if (e[1] !== '=') continue;
        const a = e.charCodeAt(0) - 97, b = e.charCodeAt(3) - 97;
        adj[a].push(b);
        adj[b].push(a);
    }
    // For each "!=", search from one letter. If the other letter is reachable,
    // a chain of "==" makes them equal, so the "!=" is broken.
    for (const e of equations) {
        if (e[1] !== '!') continue;
        const from = e.charCodeAt(0) - 97, to = e.charCodeAt(3) - 97;
        const seen: boolean[] = new Array(26).fill(false);
        const q: number[] = [from];
        seen[from] = true;
        let head = 0;
        while (head < q.length) {
            const u = q[head++];
            for (const v of adj[u]) {
                if (!seen[v]) {
                    seen[v] = true;
                    q.push(v);
                }
            }
        }
        if (seen[to]) return false;
    }
    return true;
}

Complexity

Time O(N · (26 + N))Space O(26 + N)

N = equations.length. Each != runs one search over at most 26 letters and at most N == edges. The graph itself is built once in O(N).

Optimized approach

Idea

Start from brute force

The brute runs a fresh search for every !=. The DSU joins all == pairs once, and then each != needs only two find calls.

Find the repeated work

Every != search walks the same == links again. Those links only ever join groups, so one union pass captures everything the searches would have found.

Define the state — what variables do I need?

parent[0..25]: One slot per letter a..z. Following parent up reaches the root, and the root names the letter's group.
phase: Phase 1 unites every `==`. Phase 2 checks every `!=` in input order.

Define validity

After every == is merged, two letters are forced equal exactly when they share a root, so a != between them is a contradiction.

Define the transitions — when does each pointer move, and why is it safe?

Phase 1: an equation x==y

unite(x, y)

Joins the two groups. The order of the == pairs does not matter, because joining is order-free.

Phase 2: an equation x!=y

if find(x) == find(y), return false

The same root means a chain of == links x and y, so they must be equal, which contradicts !=.

End of phase 2

return true

Every != has two different roots, so no != is forced to fail.

What does the current window add to the answer?

Phase 1 builds the groups. Phase 2 decides the answer with two find calls per !=.

Code & Implementation

optimal.cpp

// Union-Find (Disjoint Set Union) with path compression + union by size.
struct DSU {
    vector<int> parent, sz;
    int groups;
    DSU(int n) : parent(n), sz(n, 1), groups(n) { iota(parent.begin(), parent.end(), 0); }

    int find(int x) {                              // the root that names x's group
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];         // path compression (halving): skip a level each step
            x = parent[x];
        }
        return x;
    }

    bool unite(int a, int b) {                     // false when a and b were already in one group
        a = find(a), b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);             // hang the smaller tree under the bigger one
        parent[b] = a;
        sz[a] += sz[b];
        groups--;
        return true;
    }
};

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        DSU dsu(26);                               // one node per letter a..z
        // Phase 1: every "==" first, so each group of equal letters is complete.
        for (auto& e : equations)
            if (e[1] == '=') dsu.unite(e[0] - 'a', e[3] - 'a');
        // Phase 2: a "!=" is broken only when both letters already share a root.
        // The root is the final answer for the group, so this check is safe after phase 1.
        for (auto& e : equations)
            if (e[1] == '!' && dsu.find(e[0] - 'a') == dsu.find(e[3] - 'a')) return false;
        return true;
    }
};

import java.util.*;

// Union-Find (Disjoint Set Union) with path compression + union by size.
class DSU {
    int[] parent, sz;
    int groups;

    public DSU(int n) {
        parent = new int[n];
        sz = new int[n];
        groups = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    public int find(int x) {                              // the root that names x's group
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];         // path compression (halving): skip a level each step
            x = parent[x];
        }
        return x;
    }

    public boolean unite(int a, int b) {                     // false when a and b were already in one group
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) {
            int tmp = a; a = b; b = tmp;             // hang the smaller tree under the bigger one
        }
        parent[b] = a;
        sz[a] += sz[b];
        groups--;
        return true;
    }
}

class Solution {
    public boolean equationsPossible(String[] equations) {
        DSU dsu = new DSU(26);                               // one node per letter a..z
        // Phase 1: every "==" first, so each group of equal letters is complete.
        for (String e : equations) {
            if (e.charAt(1) == '=') dsu.unite(e.charAt(0) - 'a', e.charAt(3) - 'a');
        }
        // Phase 2: a "!=" is broken only when both letters already share a root.
        // The root is the final answer for the group, so this check is safe after phase 1.
        for (String e : equations) {
            if (e.charAt(1) == '!' && dsu.find(e.charAt(0) - 'a') == dsu.find(e.charAt(3) - 'a')) {
                return false;
            }
        }
        return true;
    }
}

from typing import List

# Union-Find (Disjoint Set Union) with path compression + union by size.
class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.sz = [1] * n
        self.groups = n

    def find(self, x: int) -> int:                              # the root that names x's group
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]         # path compression (halving): skip a level each step
            x = self.parent[x]
        return x

    def unite(self, a: int, b: int) -> bool:                     # false when a and b were already in one group
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return False
        if self.sz[a] < self.sz[b]:
            a, b = b, a                                         # hang the smaller tree under the bigger one
        self.parent[b] = a
        self.sz[a] += self.sz[b]
        self.groups -= 1
        return True

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        dsu = DSU(26)                               # one node per letter a..z
        # Phase 1: every "==" first, so each group of equal letters is complete.
        for e in equations:
            if e[1] == '=':
                dsu.unite(ord(e[0]) - ord('a'), ord(e[3]) - ord('a'))
        # Phase 2: a "!=" is broken only when both letters already share a root.
        # The root is the final answer for the group, so this check is safe after phase 1.
        for e in equations:
            if e[1] == '!' and dsu.find(ord(e[0]) - ord('a')) == dsu.find(ord(e[3]) - ord('a')):
                return False
        return True

// Union-Find (Disjoint Set Union) with path compression + union by size.
class DSU {
    parent: number[];
    sz: number[];
    groups: number;

    constructor(n: number) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.sz = new Array(n).fill(1);
        this.groups = n;
    }

    find(x: number): number {                              // the root that names x's group
        while (this.parent[x] !== x) {
            this.parent[x] = this.parent[this.parent[x]];  // path compression (halving): skip a level each step
            x = this.parent[x];
        }
        return x;
    }

    unite(a: number, b: number): boolean {                 // false when a and b were already in one group
        a = this.find(a);
        b = this.find(b);
        if (a === b) return false;
        if (this.sz[a] < this.sz[b]) {
            const tmp = a; a = b; b = tmp;                 // hang the smaller tree under the bigger one
        }
        this.parent[b] = a;
        this.sz[a] += this.sz[b];
        this.groups--;
        return true;
    }
}

export function equationsPossible(equations: string[]): boolean {
    const dsu = new DSU(26);                               // one node per letter a..z
    // Phase 1: every "==" first, so each group of equal letters is complete.
    for (const e of equations) {
        if (e[1] === '=') dsu.unite(e.charCodeAt(0) - 97, e.charCodeAt(3) - 97);
    }
    // Phase 2: a "!=" is broken only when both letters already share a root.
    // The root is the final answer for the group, so this check is safe after phase 1.
    for (const e of equations) {
        if (e[1] === '!' && dsu.find(e.charCodeAt(0) - 97) === dsu.find(e.charCodeAt(3) - 97)) {
            return false;
        }
    }
    return true;
}

Complexity

Time O(N · α)Space O(1)

N = equations.length. α is the inverse Ackermann function, below 5 for any input. The DSU has one slot per letter (26 in all), so the space does not grow with the input.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	BFS over the == links from one letter, once for each !=	O(N · (26 + N))	O(26 + N)
Optimal	Union-Find: merge every == pair, then fail a != whose letters share a root	O(N · α)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“x == y”Joins x and y into one group. Equal is transitive, so the group grows along chains of `==`.
“x != y”A rule to check against the finished groups, not something to union.
“can all the equations hold together”One contradiction is enough to return false, and no contradiction means true.

Equal is transitive: a==b and b==c make a==c+Every != must join two different groups+Groups come from the == pairs only→Union-Find (equivalence) — union every equality, then check the inequalities

This is the grouping by equivalence sub-pattern, where == links become unions. What makes this one different from its neighbours is order: the check for != must wait until every == has been merged, because a later == can join two letters that an earlier != looked at. Accounts Merge only needs the unions. Here the != pairs are a test on the finished groups, so they run second. Compare roots with find(x) == find(y), not with parent[x] == parent[y], because a letter can sit two steps below its root.

Don't make this mistake

Checking the != in input order, in the same loop as the ==

✗ for (auto& e : equations) { if (e[1] == '!' && dsu.find(e[0] - 'a') == dsu.find(e[3] - 'a')) return false; if (e[1] == '=') dsu.unite(e[0] - 'a', e[3] - 'a'); } return true;

✓ for (auto& e : equations) if (e[1] == '=') dsu.unite(e[0] - 'a', e[3] - 'a'); for (auto& e : equations) if (e[1] == '!' && dsu.find(e[0] - 'a') == dsu.find(e[3] - 'a')) return false; return true;

This is the pattern-confusion trap. On ["a!=b", "a==c", "c==b"] the first equation is checked while a and b are still separate, so nothing fails. Then a==c and c==b join a, c and b into one group, but the loop has already passed a!=b. It returns true, and the answer is false.

Skipping the check for a!=a

✗ if (e[1] == '!' && e[0] != e[3] && dsu.find(e[0] - 'a') == dsu.find(e[3] - 'a')) return false;

✓ if (e[1] == '!' && dsu.find(e[0] - 'a') == dsu.find(e[3] - 'a')) return false;

A letter is never different from itself, so ["a!=a"] must return false. The plain find check already does that, since find(a) == find(a). The extra e[0] != e[3] test turns it into true.

Comparing parents instead of roots

✗ if (e[1] == '!' && dsu.parent[e[0] - 'a'] == dsu.parent[e[3] - 'a']) return false;

✓ if (e[1] == '!' && dsu.find(e[0] - 'a') == dsu.find(e[3] - 'a')) return false;

parent[x] is only one step up, not the group name. On ["a==b", "c==d", "b==d", "a!=d"] the unions leave parent[a] = a and parent[d] = c, so the parent check says a and d differ and returns true. But d sits under c, and c sits under a, so find(d) = a and the answer is false.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Union-Find (DSU) translate into production architectures and low-level memory mechanics.

LLD Architecture