Watch 10 video solutions for Satisfiability of Equality Equations, a medium level problem involving Array, String, Union Find. This walkthrough by codestorywithMIK has 21,879 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |