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 <= 500equations[i].length == 4equations[i][0] is a lowercase letter.equations[i][1] is either '=' or '!'.equations[i][2] is '='.equations[i][3] is a lowercase letter.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.
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:
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.
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.
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:
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.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Union-Find Data Structure | Time Complexity: O(n * α(n)) where n is the number of equations, and α is the inverse Ackermann function. |
| 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. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find Data Structure | O(n * α(26)) ≈ O(n) | O(1) | Best general solution for equality constraints and connectivity problems |
| Graph Connectivity with BFS/DFS | O(n + V + E) | O(V + E) | Useful when modeling relationships explicitly as graphs or practicing traversal |
Satisfiability of Equality Equations - (GOOGLE) | Graph Concepts & Qns - 21 | Explanation+Coding • codestorywithMIK • 21,879 views views
Watch 9 more video solutions →Practice Satisfiability of Equality Equations with our built-in code editor and test cases.
Practice on FleetCode