< Back





990. Satisfiability of Equality Equations

Very fun question. We're given a list of equations of the format "a==b" or "b!=a" and we're asked to
determine if the set of equations is satisfiable. All variables in these equations are lowercase, and
the equations are only the two inequalities "==" and "!=".

To solve this, we treat "==" as an undirected edge for the two nodes represented by the variables of
the equation. We treat "==" as reflective and transitive, so if a==b and b==c, then a==c. Given this,
we can store variables that are equal in disjoint sets. When we evaluate all "!=" equations, we see
if the two variables are in the same disjoint set - this would be a contradiction for our set of
equations, so we return False. If we don't find any contradictions, we return True.

The solution is as follows:


  from collections import defaultdict

  class UnionFind:
      def __init__(self, n: int) -> None:
          self.rank, self.parent = [1 for _ in range(n)], [i for i in range(n)]

      def find(self, x: str) -> str:
          if self.parent[x] != x:
              self.parent[x] = self.find(self.parent[x])
          return self.parent[x]

      def union_set(self, x: str, y: str) -> None:
          xset, yset = self.find(x), self.find(y)

          if xset != yset:
              if self.rank[xset] < self.rank[yset]:
                  xset, yset = yset, xset

              self.parent[yset] = xset
              self.rank[xset] += self.rank[yset]

  class Solution:
      def equationsPossible(self, equations: List[str]) -> bool:
          uf = UnionFind(26)

          for equation in equations:
              if equation[1] == "=":
                  u, v = ord(equation[0]) - ord("a"), ord(equation[3]) - ord("a")
                  uf.union_set(u, v)

          for equation in equations:
              if equation[1] == "!":
                  u, v = ord(equation[0]) - ord("a"), ord(equation[3]) - ord("a")
                  if uf.find(u) == uf.find(v):
                      return False

          return True


_ Time Complexity:

  O(n) - We execute find or union_set at most n times.

_ Space Complexity:

  O(1) - Our storage requirements are constant, 26 characters.