Satisfiability of Equality Equations

Med

#0944Time: O(N + V), where N is the number of equations and V is the number of variables (26). Building the graph takes O(N). Finding connected components takes O(V + E) where E is the number of equalities (E <= N). Checking inequalities takes O(N). The total is O(N+V). Since V is constant, this is O(N).Space: O(N + V), where N is the number of equations and V is the number of variables (26). The adjacency list can store O(N) edges, and the list of inequalities can also be O(N). Since V is constant, this simplifies to O(N).2 companies

Algorithms

Union Find

Data structures

Array String Graph

Companies

UiPath Sumo Logic

Prompt

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: "x_i==y_i" or "x_i!=y_i".Here, x_i and y_i 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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach models the problem using a graph. Variables are treated as vertices, and an == relation forms an edge between them. The goal is to find connected components in this graph. If any two variables in a != relation belong to the same connected component, it signifies a contradiction.

Algorithm

Create an adjacency list adj to represent a graph where vertices are the 26 lowercase letters.
Create a separate list to store all inequality (!=) equations.
Iterate through the input equations. For each x == y, add an undirected edge between x and y in the adjacency list. For each x != y, add it to the inequality list.
After building the graph, find its connected components using a graph traversal algorithm like Depth-First Search (DFS) or Breadth-First Search (BFS).
Use a componentId array of size 26 to store the component ID for each variable. Initialize all IDs to a sentinel value (e.g., 0).
Iterate through all variables from 'a' to 'z'. If a variable has not been visited (its component ID is 0), start a traversal (e.g., DFS) from it. Assign a new, unique component ID to all vertices reachable in this traversal.
Finally, iterate through the stored inequality list. For each x != y, check if x and y belong to the same component by comparing their IDs in the componentId array.
If componentId[x] == componentId[y], it implies x and y are connected by a path of == relations, meaning they must be equal. This contradicts the x != y constraint, so return false.
If all inequalities are checked without finding a contradiction, return true.

Walkthrough

In this method, we first separate the equations into two groups: equalities (==) and inequalities (!=). We use the equality equations to build an undirected graph where each variable is a node and an edge exists between two nodes if they are stated to be equal. All variables within a single connected component of this graph must have the same value due to the transitive nature of equality (a==b and b==c implies a==c).

We can find these connected components using a standard graph traversal algorithm like DFS or BFS. We assign a unique ID to each component and store which component each variable belongs to in an array.

After identifying the components, we check the inequality equations. For each x != y, we look up the component IDs of x and y. If they have the same component ID, it means we have derived x == y from the equality equations, which contradicts the x != y constraint. In this case, the set of equations is unsatisfiable, and we return false. If we process all inequalities without finding such a conflict, the equations are satisfiable, and we return true.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public boolean equationsPossible(String[] equations) {6        List<Integer>[] adj = new ArrayList[26];7        for (int i = 0; i < 26; i++) {8            adj[i] = new ArrayList<>();9        }10 11        List<int[]> inequalities = new ArrayList<>();12 13        for (String eq : equations) {14            int u = eq.charAt(0) - 'a';15            int v = eq.charAt(3) - 'a';16            if (eq.charAt(1) == '=') {17                adj[u].add(v);18                adj[v].add(u);19            } else {20                inequalities.add(new int[]{u, v});21            }22        }23 24        int[] componentId = new int[26];25        int currentId = 1;26        for (int i = 0; i < 26; i++) {27            if (componentId[i] == 0) {28                dfs(i, currentId, adj, componentId);29                currentId++;30            }31        }32 33        for (int[] inequality : inequalities) {34            int u = inequality[0];35            int v = inequality[1];36            if (componentId[u] == componentId[v]) {37                return false;38            }39        }40 41        return true;42    }43 44    private void dfs(int u, int id, List<Integer>[] adj, int[] componentId) {45        componentId[u] = id;46        for (int v : adj[u]) {47            if (componentId[v] == 0) {48                dfs(v, id, adj, componentId);49            }50        }51    }52}

Complexity

Time

O(N + V), where N is the number of equations and V is the number of variables (26). Building the graph takes O(N). Finding connected components takes O(V + E) where E is the number of equalities (E <= N). Checking inequalities takes O(N). The total is O(N+V). Since V is constant, this is O(N).

Space

O(N + V), where N is the number of equations and V is the number of variables (26). The adjacency list can store O(N) edges, and the list of inequalities can also be O(N). Since V is constant, this simplifies to O(N).

Trade-offs

Pros

Conceptually clear and builds upon fundamental graph traversal algorithms.
Correctly solves the problem by identifying equivalence classes.

Cons

Requires more space (O(N)) compared to the Union-Find approach due to the need to store the graph's adjacency list and the list of inequalities.
The implementation can be slightly more verbose, involving graph data structures and traversal logic.

A more optimized approach uses the Union-Find data structure to efficiently group variables. We process all equality (==) equations first to union variables into sets. Then, we check the inequality (!=) equations. A contradiction occurs if two variables in a != relation belong to the same set.

Algorithm

Initialize a Union-Find (or Disjoint Set Union) data structure for 26 elements, representing the variables 'a' through 'z'. Each variable starts in its own set.
Make a first pass through the equations array. For every equality equation x == y, perform a union operation on the sets containing x and y. This merges their sets, reflecting that they must be equal. After this pass, all variables that are transitively equal will belong to the same set, identified by a common root.
Make a second pass through the equations array. This time, consider only the inequality equations x != y.
For each inequality, use the find operation to get the representatives (roots) of the sets for x and y.
If find(x) == find(y), it means x and y are in the same set due to the equality relations. This implies x == y, which contradicts the x != y constraint. Return false immediately.
If the second pass completes without finding any contradictions, it means the equations are satisfiable. Return true.

Walkthrough

The Union-Find data structure is perfectly suited for problems involving equivalence relations and partitioning elements into disjoint sets. Here, the == relation defines equivalence classes.

We can represent the 26 variables as integers 0-25. The algorithm proceeds in two main phases:

Union Phase: We iterate through all equations. If we encounter an equality x == y, we merge the sets containing x and y using the union operation. This step effectively groups all variables that must have the same value into the same component or set.
Check Phase: After processing all equalities, we iterate through the equations again. This time, we look for inequalities x != y. For each one, we check if x and y belong to the same set by comparing the results of find(x) and find(y). The find operation returns the representative (or root) of the set an element belongs to. If the representatives are the same, it means x and y are in the same group, implying x == y. This is a contradiction, so we return false.

If we successfully check all inequalities without finding a contradiction, it means a consistent assignment is possible, so we return true. This approach is highly efficient because Union-Find operations with optimizations like path compression and union by rank/size are nearly constant time on average.

1class Solution {2    private int[] parent;3 4    // Find operation with path compression5    private int find(int i) {6        if (parent[i] == i) {7            return i;8        }9        return parent[i] = find(parent[i]);10    }11 12    // Union operation (can be improved with union by size/rank)13    private void union(int i, int j) {14        int rootI = find(i);15        int rootJ = find(j);16        if (rootI != rootJ) {17            parent[rootI] = rootJ;18        }19    }20 21    public boolean equationsPossible(String[] equations) {22        parent = new int[26];23        for (int i = 0; i < 26; i++) {24            parent[i] = i;25        }26 27        // 1. Process all '==' equations28        for (String eq : equations) {29            if (eq.charAt(1) == '=') {30                int u = eq.charAt(0) - 'a';31                int v = eq.charAt(3) - 'a';32                union(u, v);33            }34        }35 36        // 2. Process all '!=' equations37        for (String eq : equations) {38            if (eq.charAt(1) == '!') {39                int u = eq.charAt(0) - 'a';40                int v = eq.charAt(3) - 'a';41                if (find(u) == find(v)) {42                    return false; // Contradiction43                }44            }45        }46 47        return true;48    }49}

Complexity

Time

O(N * α(V)), where N is the number of equations, V is the number of variables (26), and α is the extremely slow-growing Inverse Ackermann function. For all practical purposes, α(V) is a small constant (< 5), making the time complexity effectively linear, O(N).

Space

O(V), where V is the number of variables (26). The Union-Find data structure requires an array of size V to store the parent pointers (and another optional array for ranks/sizes). Since V is a fixed constant, the space complexity is O(1).

Trade-offs

Pros

Extremely efficient, with nearly constant-time operations on average.
Optimal space complexity, requiring only O(V) space, which is O(1) for this problem.
The implementation is often more concise and elegant than the graph-based approach.

Cons

Requires understanding the Union-Find data structure, which may be less familiar than basic graph traversal.

Solutions

Solution

1class Solution {2private3  int[] p;4public5  boolean equationsPossible(String[] equations) {6    p = new int[26];7    for (int i = 0; i < 26; ++i) {8      p[i] = i;9    }10    for (String e : equations) {11      int a = e.charAt(0) - 'a', b = e.charAt(3) - 'a';12      if (e.charAt(1) == '=') {13        p[find(a)] = find(b);14      }15    }16    for (String e : equations) {17      int a = e.charAt(0) - 'a', b = e.charAt(3) - 'a';18      if (e.charAt(1) == '!' && find(a) == find(b)) {19        return false;20      }21    }22    return true;23  }24private25  int find(int x) {26    if (p[x] != x) {27      p[x] = find(p[x]);28    }29    return p[x];30  }31}

1class Solution {2public:3  vector<int> p;4  bool equationsPossible(vector<string> &equations) {5    p.resize(26);6    for (int i = 0; i < 26; ++i)7      p[i] = i;8    for (auto &e : equations) {9      int a = e[0] - 'a', b = e[3] - 'a';10      if (e[1] == '=')11        p[find(a)] = find(b);12    }13    for (auto &e : equations) {14      int a = e[0] - 'a', b = e[3] - 'a';15      if (e[1] == '!' && find(a) == find(b))16        return false;17    }18    return true;19  }20  int find(int x) {21    if (p[x] != x)22      p[x] = find(p[x]);23    return p[x];24  }25};

1class Solution:2    def equationsPossible(self, equations: List[str]) -> bool: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] p = list(range(26)) for e in equations: a, b = ord(e[0]) - ord('a'), ord(e[- 1]) - ord('a') if e[1] == '=': p[find(a)] = find(b) for e in equations: a, b = ord(e[0]) - ord('a'), ord(e[- 1]) - ord('a') if e[1] == '!' and find(a) == find(b): return False return True

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem