Skip to main content
Talentd

Satisfiability of Equality Equations - Solution & Explanation

MediumArrayStringUnion FindGraph21 min readAsked at: Amazon, Meta, Google +3
Practice this problem

Problem Statement

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.

The solution uses two functions find and unionSet to implement the Union-Find operations. Each variable is initially its own parent. For each '==' equation, the unionSet function connects the two variables. For each '!=' equation, the find function checks if both variables are connected, returning false if they are, because they shouldn't be connected. The program finally returns true if no such pairs exist.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * α(n)) where n is the number of equations, and α is the inverse Ackermann function.
Space Complexity: O(1) as we are using a fixed-size array of 26 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.

This C solution constructs an undirected graph for the equality constraints and checks inequality constraints using a BFS traversal. If any graph component contains both nodes linked by a '!=' relation, it returns false. The operation checks conflicts and resets visitation states for independent inequality checks.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the number of equations as each one is processed once during graph building and inequality checks.
Space Complexity: O(1) as it uses a fixed-size 26x26 adjacency matrix.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

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) as we are using a fixed-size array of 26 characters.

Graph Connectivity with BFS

Time Complexity: O(n) where n is the number of equations as each one is processed once during graph building and inequality checks.
Space Complexity: O(1) as it uses a fixed-size 26x26 adjacency matrix.

Default Approach—

Detailed 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

Video Solution

Satisfiability of Equality Equations - (GOOGLE) | Graph Concepts & Qns - 21 | Explanation+Coding • codestorywithMIK • 25,726 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Satisfiability of Equality Equations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays