Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Satisfiability of Equality Equations solution and explanation

MediumArrayGraphStringUnion Find6 min read52.2% acceptanceUpdated 9 Apr 2026
Asked atSumo LogicUiPathClevertapAmazonGoogleMeta
Practise Satisfiability of Equality Equations
20:08
Satisfiability of Equality Equations - (GOOGLE) | Graph Concepts & Qns - 21 | Explanation+CodingcodestorywithMIK · 20:08 · 25K viewsWatch on YouTube
9 more videos on this problem
  1. Satisfiability of Equality Equations - (GOOGLE) | Graph Concepts & Qns - 21 | Explanation+CodingcodestorywithMIK · 20:08 · 25K views
  2. LeetCode 990 | Satisfiability of Equality Equationsleetuition · 16:31 · 3K views
  3. Leetcode 990 Satisfiability of Equality Equations | DP Coding Decoded SDE SheetCoding Decoded · 6:07 · 2K views
  4. 990. Satisfiability of Equality Equations || DSA || Leetcode Daily Challenge || Code in descriptionLeetcode Daily Challenge · 6:30 · 2K views
  5. Daily Leetcode #909: Sep 26, 2022 - 990. Satisfiability of Equality EquationsProgramming Live with Larry · 6:06 · 1K views
  6. Satisfiability of Equality Equations | Top Google Coding Interview QuestionCoding Courses · 9:32 · 917 views
  7. 990. Satisfiability of Equality Equations | LeetCode Solution | Java Solution with Time ComplexityShrayansh Jain · 16:12 · 636 views
  8. Leetcode 990: Satisfiability of Equality EquationsAlgorithms Casts · 14:01 · 553 views
  9. 990. Satisfiability of Equality EquationsTechBayArea · 17:30 · 478 views
  10. 990. Satisfiability of Equality Equations 等式方程的可满足性【LeetCode 力扣题解】LeetCode 力扣 · 9:16 · 369 views

The problem

You are given an array of strings equations that represent relationships between variables where each string equations[i] is of length 4 and takes one of two different forms: "xi==yi" or "xi!=yi".Here, xi and yi are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if it is possible to assign integers to variable names so as to satisfy all the given equations, or false otherwise.

Example 1:

Input: equations = ["a==b","b!=a"]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.
There is no way to assign the variables to satisfy both equations.

Example 2:

Input: equations = ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

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.

Approach overview

Problem Overview: You receive equations like a==b or a!=b involving lowercase variables. The task is to determine whether all equations can be satisfied simultaneously without contradictions.

Approach 1: Union-Find Data Structure (O(n) time, O(1) space)

This problem is essentially about grouping variables that must be equal and verifying that inequalities do not break those groups. Use a Union-Find (Disjoint Set Union) structure with 26 nodes representing characters a to z. First iterate through all equations and union the variables for every equality (==). After building these connected components, iterate again and check inequalities (!=). If two variables that must be different belong to the same parent set, the system is inconsistent.

The key insight: equalities define connected components, and inequalities must never appear inside the same component. Union-Find handles merging and parent lookups in near constant time using path compression. Since there are only 26 possible variables, space remains constant and the runtime becomes O(n * α(26)), effectively O(n). This is the cleanest and most common solution used in interviews.

Approach 2: Graph Connectivity with BFS (O(n + V + E) time, O(V + E) space)

Another way to model the problem is with a graph. Treat each variable as a node and connect nodes with edges for every equality equation. After building the graph, each connected component represents variables that must share the same value. For every inequality equation, run a BFS or DFS to check whether both variables are reachable within the same component.

If BFS finds a path between two variables that must be different, the equations cannot be satisfied. Otherwise the system is valid. The graph approach makes the connectivity relationship explicit and is useful if you're already comfortable solving problems using traversal algorithms like BFS or DFS.

The complexity depends on graph size. With at most 26 nodes, traversal is cheap, but the algorithm still requires storing adjacency lists and performing searches for inequalities.

Recommended for interviews: Union-Find is the expected approach. It models equality relationships directly as disjoint sets and resolves conflicts in nearly constant time. Interviewers usually want to see that you recognize this as a connectivity problem and apply Union-Find. The graph traversal approach also works and demonstrates understanding of connected components, but it is slightly heavier than necessary.

Approach 1: Union-Find Data Structure

This approach uses the Union-Find data structure to manage connectivity between variables. The core idea is to group variables that are known to be equal using '=='. After processing all such equations, we then check the '!=' equations to ensure that connected variables (i.e., variables that are in the same component) are not incorrectly marked as not equal.

Steps:

  • Create a Union-Find structure for 26 possible lowercase variables.
  • For each '==' equation, perform a union operation to connect the variables.
  • For each '!=' equation, check if the two variables are connected (i.e., have the same root). If they are, return false.
  • If no conflicts are found, return true.
class Solution:
    def find(self, parent, x):
        if parent[x] != x:
            parent[x] = self.find(parent, parent[x])
        return parent[x]

    def union(self, parent, x, y):
        rootX = self.find(parent, x)
        rootY = self.find(parent, y)
        if rootX != rootY:
            parent[rootY] = rootX

    def equationsPossible(self, equations):
        parent = list(range(26))

        for eq in equations:
            if eq[1] == '=':
                index1 = ord(eq[0]) - ord('a')
                index2 = ord(eq[3]) - ord('a')
                self.union(parent, index1, index2)

        for eq in equations:
            if eq[1] == '!':
                index1 = ord(eq[0]) - ord('a')
                index2 = ord(eq[3]) - ord('a')
                if self.find(parent, index1) == self.find(parent, index2):
                    return False

        return True
class Solution {
    public int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }

    public void unionSet(int[] parent, int x, int y) {
        int rootX = find(parent, x);
        int rootY = find(parent, y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }

    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) == '=') {
                int index1 = eq.charAt(0) - 'a';
                int index2 = eq.charAt(3) - 'a';
                unionSet(parent, index1, index2);
            }
        }

        for (String eq : equations) {
            if (eq.charAt(1) == '!') {
                int index1 = eq.charAt(0) - 'a';
                int index2 = eq.charAt(3) - 'a';
                if (find(parent, index1) == find(parent, index2)) {
                    return false;
                }
            }
        }
        return true;
    }
}
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    int find(vector<int>& parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }

    void unionSet(vector<int>& parent, int x, int y) {
        int rootX = find(parent, x);
        int rootY = find(parent, y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }

    bool equationsPossible(vector<string>& equations) {
        vector<int> parent(26);
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }

        for (const string& eq : equations) {
            if (eq[1] == '=') {
                int index1 = eq[0] - 'a';
                int index2 = eq[3] - 'a';
                unionSet(parent, index1, index2);
            }
        }

        for (const string& eq : equations) {
            if (eq[1] == '!') {
                int index1 = eq[0] - 'a';
                int index2 = eq[3] - 'a';
                if (find(parent, index1) == find(parent, index2)) {
                    return false;
                }
            }
        }
        return true;
    }
};
var equationsPossible = function(equations) {
    let parent = new Array(26).fill(0).map((_, index) => index);

    const find = (x) => {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    const union = (x, y) => {
        let rootX = find(x);
        let rootY = find(y);
        if (rootX !== rootY) {
            parent[rootY] = rootX;
        }
    }

    equations.forEach(eq => {
        if (eq[1] === '=') {
            let index1 = eq.charCodeAt(0) - 'a'.charCodeAt(0);
            let index2 = eq.charCodeAt(3) - 'a'.charCodeAt(0);
            union(index1, index2);
        }
    });

    for (let eq of equations) {
        if (eq[1] === '!') {
            let index1 = eq.charCodeAt(0) - 'a'.charCodeAt(0);
            let index2 = eq.charCodeAt(3) - 'a'.charCodeAt(0);
            if (find(index1) === find(index2)) {
                return false;
            }
        }
    }
    return true;
};
#include <stdbool.h>
#include <string.h>

int find(int parent[], int x) {
    if (parent[x] != x) {
        parent[x] = find(parent, parent[x]);
    }
    return parent[x];
}

void unionSet(int parent[], int x, int y) {
    int rootX = find(parent, x);
    int rootY = find(parent, y);
    if (rootX != rootY) {
        parent[rootY] = rootX;
    }
}

bool equationsPossible(char ** equations, int equationsSize) {
    int parent[26];
    for (int i = 0; i < 26; i++) {
        parent[i] = i;
    }
    
    // Handle the '==' equations first
    for (int i = 0; i < equationsSize; i++) {
        if (equations[i][1] == '=') {
            int index1 = equations[i][0] - 'a';
            int index2 = equations[i][3] - 'a';
            unionSet(parent, index1, index2);
        }
    }

    // Then, handle the '!=' equations
    for (int i = 0; i < equationsSize; i++) {
        if (equations[i][1] == '!') {
            int index1 = equations[i][0] - 'a';
            int index2 = equations[i][3] - 'a';
            if (find(parent, index1) == find(parent, index2)) {
                return false;
            }
        }
    }
    return true;
}
public class Solution {
    public int Find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent, parent[x]);
        }
        return parent[x];
    }

    public void Union(int[] parent, int x, int y) {
        int rootX = Find(parent, x);
        int rootY = Find(parent, y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }

    public bool EquationsPossible(string[] equations) {
        int[] parent = new int[26];
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }

        foreach (var eq in equations) {
            if (eq[1] == '=') {
                int index1 = eq[0] - 'a';
                int index2 = eq[3] - 'a';
                Union(parent, index1, index2);
            }
        }

        foreach (var eq in equations) {
            if (eq[1] == '!') {
                int index1 = eq[0] - 'a';
                int index2 = eq[3] - 'a';
                if (Find(parent, index1) == Find(parent, index2)) {
                    return false;
                }
            }
        }
        return true;
    }
}

The Python solution employs similar methods to handle union and find operations. The character indices are calculated using ord to map variable names to indices. Therefore, we use these indices for connectivity checks and operations.

Complexity

Time Complexity: O(n * α(n)) where n is the number of equations, and α is the inverse Ackermann function.
Space Complexity: O(1) with a fixed-size list for all lowercase characters.

Try this approach in the editor

Approach 2: Graph Connectivity with BFS

Another method is to visualize the problem as a graph and determine if the '==' relations create valid partitions without violating '!=' conditions. This is managed using a BFS approach.

Steps:

  • Create a graph using adjacency lists, where each node connects if there's an equality.
  • Use BFS to traverse connected components.
  • Check if any inequality binds points within the same component, marking a conflict.
  • Return true if no invalid equality is in place.
class Solution:
    def bfsCheck(self, graph, visited, start, target):
        from collections import deque
        queue = deque([start])
        visited[start] = True
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if not visited[v]:
                    if v == target:
                        return True
                    visited[v] = True
                    queue.append(v)
        return False
    
    def equationsPossible(self, equations):
        graph = [[] for _ in range(26)]
        visited = [False] * 26

        for eq in equations:
            if eq[1] == '=':
                u = ord(eq[0]) - ord('a')
                v = ord(eq[3]) - ord('a')
                graph[u].append(v)
                graph[v].append(u)

        for eq in equations:
            if eq[1] == '!':
                u = ord(eq[0]) - ord('a')
                v = ord(eq[3]) - ord('a')
                if self.bfsCheck(graph, visited, u, v):
                    return False
                visited = [False] * 26

        return True
import java.util.*;

class Solution {
    private boolean bfsCheck(List<Integer>[] graph, boolean[] visited, int start, int target) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : graph[u]) {
                if (!visited[v]) {
                    if (v == target) return true;
                    visited[v] = true;
                    queue.offer(v);
                }
            }
        }
        return false;
    }

    public boolean equationsPossible(String[] equations) {
        List<Integer>[] graph = new ArrayList[26];
        for (int i = 0; i < 26; i++) {
            graph[i] = new ArrayList<>();
        }
        boolean[] visited = new boolean[26];

        for (String eq : equations) {
            if (eq.charAt(1) == '=') {
                int u = eq.charAt(0) - 'a';
                int v = eq.charAt(3) - 'a';
                graph[u].add(v);
                graph[v].add(u);
            }
        }

        for (String eq : equations) {
            if (eq.charAt(1) == '!') {
                int u = eq.charAt(0) - 'a';
                int v = eq.charAt(3) - 'a';
                if (bfsCheck(graph, visited, u, v)) {
                    return false;
                }
                Arrays.fill(visited, false);
            }
        }
        return true;
    }
}
#include <vector>
#include <string>
#include <queue>
#include <cstring>
using namespace std;

class Solution {
public:
    bool bfsCheck(vector<vector<int>>& graph, vector<bool>& visited, int start, int target) {
        queue<int> q;
        q.push(start);
        visited[start] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v = 0; v < 26; ++v) {
                if (graph[u][v] && !visited[v]) {
                    if (v == target) return true;
                    visited[v] = true;
                    q.push(v);
                }
            }
        }
        return false;
    }
    
    bool equationsPossible(vector<string>& equations) {
        vector<vector<int>> graph(26, vector<int>(26, 0));
        vector<bool> visited(26, false);

        for (const auto& eq : equations) {
            if (eq[1] == '=') {
                int u = eq[0] - 'a';
                int v = eq[3] - 'a';
                graph[u][v] = graph[v][u] = 1;
            }
        }

        for (const auto& eq : equations) {
            if (eq[1] == '!') {
                int u = eq[0] - 'a';
                int v = eq[3] - 'a';
                if (bfsCheck(graph, visited, u, v)) {
                    return false;
                }
                fill(visited.begin(), visited.end(), false);
            }
        }

        return true;
    }
};
var equationsPossible = function(equations) {
    const graph = Array.from({ length: 26 }, () => []);

    const bfsCheck = (start, target) => {
        const queue = [start];
        const visited = Array(26).fill(false);
        visited[start] = true;

        while (queue.length !== 0) {
            const u = queue.shift();
            for (const v of graph[u]) {
                if (!visited[v]) {
                    if (v === target) return true;
                    visited[v] = true;
                    queue.push(v);
                }
            }
        }

        return false;
    };

    for (const eq of equations) {
        if (eq.charAt(1) === '=') {
            const u = eq.charCodeAt(0) - 'a'.charCodeAt(0);
            const v = eq.charCodeAt(3) - 'a'.charCodeAt(0);
            graph[u].push(v);
            graph[v].push(u);
        }
    }

    for (const eq of equations) {
        if (eq.charAt(1) === '!') {
            const u = eq.charCodeAt(0) - 'a'.charCodeAt(0);
            const v = eq.charCodeAt(3) - 'a'.charCodeAt(0);
            if (bfsCheck(u, v)) {
                return false;
            }
        }
    }

    return true;
};
#include <stdbool.h>
#include <string.h>

void addEdge(int graph[][26], int u, int v) {
    graph[u][v] = 1;
    graph[v][u] = 1;
}

bool bfsCheck(int graph[][26], bool visited[], int start, int target, int V) {
    int queue[26], front = 0, back = 0;
    queue[back++] = start;
    visited[start] = true;
    while (front < back) {
        int u = queue[front++];
        for (int v = 0; v < V; v++) {
            if (graph[u][v] && !visited[v]) {
                if (v == target) return true;
                visited[v] = true;
                queue[back++] = v;
            }
        }
    }
    return false;
}

bool equationsPossible(char ** equations, int equationsSize) {
    int graph[26][26] = {0};
    bool visited[26];
    memset(visited, false, sizeof(visited));

    // Build graph for '==' equations
    for (int i = 0; i < equationsSize; i++) {
        if (equations[i][1] == '=') {
            int index1 = equations[i][0] - 'a';
            int index2 = equations[i][3] - 'a';
            addEdge(graph, index1, index2);
        }
    }

    // Check for '!='
    for (int i = 0; i < equationsSize; i++) {
        if (equations[i][1] == '!') {
            int index1 = equations[i][0] - 'a';
            int index2 = equations[i][3] - 'a';
            if (bfsCheck(graph, visited, index1, index2, 26)) {
                return false;
            }
            memset(visited, false, sizeof(visited));
        }
    }

    return true;
}
using System;
using System.Collections.Generic;

public class Solution {
    private bool bfsCheck(List<int>[] graph, bool[] visited, int start, int target) {
        var queue = new Queue<int>();
        queue.Enqueue(start);
        visited[start] = true;
        while (queue.Count > 0) {
            int u = queue.Dequeue();
            foreach (int v in graph[u]) {
                if (!visited[v]) {
                    if (v == target) return true;
                    visited[v] = true;
                    queue.Enqueue(v);
                }
            }
        }
        return false;
    }

    public bool EquationsPossible(string[] equations) {
        var graph = new List<int>[26];
        for (int i = 0; i < 26; i++) {
            graph[i] = new List<int>();
        }
        bool[] visited = new bool[26];

        foreach (var eq in equations) {
            if (eq[1] == '=') {
                int u = eq[0] - 'a';
                int v = eq[3] - 'a';
                graph[u].Add(v);
                graph[v].Add(u);
            }
        }

        foreach (var eq in equations) {
            if (eq[1] == '!') {
                int u = eq[0] - 'a';
                int v = eq[3] - 'a';
                if (bfsCheck(graph, visited, u, v)) {
                    return false;
                }
                Array.Fill(visited, false);
            }
        }

        return true;
    }
}

The Python graph implementation uses lists of lists for creating adjustable connectivity maps, engaging queues to seek connections and enforce separations via BFS processing. Each inequality discovered in the same component steps up incongruence resolutions, returning false when conflicts emerge.

Complexity

Time Complexity: O(n), visiting each equality and inequality point
Space Complexity: O(1) with regard to graph and visited tracking scope.

Try this approach in the editor

Approach 3: Default Approach

class UnionFind {
    private parent: number[];

    constructor() {
        this.parent = Array.from({ length: 26 }).map((_, i) => i);
    }

    find(index: number) {
        if (this.parent[index] === index) {
            return index;
        }
        this.parent[index] = this.find(this.parent[index]);
        return this.parent[index];
    }

    union(index1: number, index2: number) {
        this.parent[this.find(index1)] = this.find(index2);
    }
}

function equationsPossible(equations: string[]): boolean {
    const uf = new UnionFind();
    for (const [a, s, _, b] of equations) {
        if (s === '=') {
            const index1 = a.charCodeAt(0) - 'a'.charCodeAt(0);
            const index2 = b.charCodeAt(0) - 'a'.charCodeAt(0);
            uf.union(index1, index2);
        }
    }
    for (const [a, s, _, b] of equations) {
        if (s === '!') {
            const index1 = a.charCodeAt(0) - 'a'.charCodeAt(0);
            const index2 = b.charCodeAt(0) - 'a'.charCodeAt(0);
            if (uf.find(index1) === uf.find(index2)) {
                return false;
            }
        }
    }
    return true;
}
func equationsPossible(equations []string) bool {
	p := make([]int, 26)
	for i := 1; i < 26; i++ {
		p[i] = i
	}
	var find func(x int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for _, e := range equations {
		a, b := int(e[0]-'a'), int(e[3]-'a')
		if e[1] == '=' {
			p[find(a)] = find(b)
		}
	}
	for _, e := range equations {
		a, b := int(e[0]-'a'), int(e[3]-'a')
		if e[1] == '!' && find(a) == find(b) {
			return false
		}
	}
	return true
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Union-Find Data Structure

Time Complexity: O(n * α(n)) where n is the number of equations, and α is the inverse Ackermann function.
Space Complexity: O(1) with a fixed-size list for all lowercase characters.

Graph Connectivity with BFS

Time Complexity: O(n), visiting each equality and inequality point
Space Complexity: O(1) with regard to graph and visited tracking scope.

Default Approach–

Complexity analysis

ApproachTimeSpaceWhen to Use
Union-Find Data StructureO(n * α(26)) ≈ O(n)O(1)Best general solution for equality constraints and connectivity problems
Graph Connectivity with BFS/DFSO(n + V + E)O(V + E)Useful when modeling relationships explicitly as graphs or practicing traversal

Frequently asked questions

Is Satisfiability of Equality Equations easy or hard?

The problem is rated Medium on LeetCode. The challenge lies in recognizing that equality constraints form connected components and that Union-Find provides an efficient way to manage them.

Satisfiability of Equality Equations Python/Java solution

Most implementations create a Union-Find structure with 26 nodes representing characters a–z. Python and Java solutions perform union operations for '==' equations and root comparisons for '!=' equations. The logic stays identical across languages.

How to solve Satisfiability of Equality Equations in O(n)?

Process equations in two passes. First union all variables appearing in equality equations using Union-Find. Then check each inequality equation and verify that both variables do not share the same root parent. If any do, the system is unsatisfiable.

What is the best approach for Satisfiability of Equality Equations?

Union-Find (Disjoint Set Union) is the most efficient and commonly used approach. First union all variables connected by equality equations, then verify that no inequality pair belongs to the same set. With path compression, the runtime becomes nearly O(n).

Is Satisfiability of Equality Equations asked at Google/Amazon/Meta?

Connectivity and Union-Find problems similar to this appear frequently in interviews at companies like Google, Amazon, and Meta. The problem tests understanding of disjoint sets, graph connectivity, and constraint validation.

What data structure is used in Satisfiability of Equality Equations?

The primary data structure is Union-Find (Disjoint Set Union). It efficiently tracks groups of variables that must be equal. A graph representation with BFS or DFS can also solve the problem by checking connected components.

What is the time complexity of Satisfiability of Equality Equations?

The optimal Union-Find solution runs in O(n * α(26)), where α is the inverse Ackermann function. Since there are only 26 variables, this behaves like O(n) in practice. Space complexity is O(1).

Comments

Now write it yourselfClose this page and solve Satisfiability of Equality Equations in the editor, without looking.
Practise Satisfiability of Equality Equations