Scale Engineer

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
ArrayStringGraph
Companies
UiPathSumo 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: "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.

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.

import java.util.ArrayList;import java.util.List; class Solution {    public boolean equationsPossible(String[] equations) {        List<Integer>[] adj = new ArrayList[26];        for (int i = 0; i < 26; i++) {            adj[i] = new ArrayList<>();        }         List<int[]> inequalities = new ArrayList<>();         for (String eq : equations) {            int u = eq.charAt(0) - 'a';            int v = eq.charAt(3) - 'a';            if (eq.charAt(1) == '=') {                adj[u].add(v);                adj[v].add(u);            } else {                inequalities.add(new int[]{u, v});            }        }         int[] componentId = new int[26];        int currentId = 1;        for (int i = 0; i < 26; i++) {            if (componentId[i] == 0) {                dfs(i, currentId, adj, componentId);                currentId++;            }        }         for (int[] inequality : inequalities) {            int u = inequality[0];            int v = inequality[1];            if (componentId[u] == componentId[v]) {                return false;            }        }         return true;    }     private void dfs(int u, int id, List<Integer>[] adj, int[] componentId) {        componentId[u] = id;        for (int v : adj[u]) {            if (componentId[v] == 0) {                dfs(v, id, adj, componentId);            }        }    }}

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.

Solutions

class Solution {private  int[] p;public  boolean equationsPossible(String[] equations) {    p = new int[26];    for (int i = 0; i < 26; ++i) {      p[i] = i;    }    for (String e : equations) {      int a = e.charAt(0) - 'a', b = e.charAt(3) - 'a';      if (e.charAt(1) == '=') {        p[find(a)] = find(b);      }    }    for (String e : equations) {      int a = e.charAt(0) - 'a', b = e.charAt(3) - 'a';      if (e.charAt(1) == '!' && find(a) == find(b)) {        return false;      }    }    return true;  }private  int find(int x) {    if (p[x] != x) {      p[x] = find(p[x]);    }    return p[x];  }}

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 →

Next problem