Satisfiability of Equality Equations

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.


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


We will use DSU for this question with two passes on equations.

In the first pass, we join the variables that are equal into one component. In the second pass, we check whether two variables in an inequality expression are indeed in different components. If we arrive at a contradition, then the equality equations are not satisfiable.


1def equationsPossible(self, equations: List[str]) -> bool:
2    equality = {}
3    def find(x):
4        y = equality.get(x, x)
5        if y != x:
6            equality[x] = y = find(y)
7        return y
8    def union(x, y):
9        equality[find(x)] = find(y)
11    for eq in equations:
12        if eq[1] == '=':
13            union(eq[0], eq[3])
14    for eq in equations:
15        if eq[1] == '!' and find(eq[0]) == find(eq[3]):
16            return False
17    return True    
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Solution Implementation

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer techniques do you use to check if a string is a palindrome?

Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.