# Satisfiability of Equality Equations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/satisfiability-of-equality-equations)
Canonical: https://scaleengineer.com/dsa/problems/satisfiability-of-equality-equations
**Algorithms:** [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, String, Graph
**Companies:** [UiPath](https://scaleengineer.com/companies/uipath), [Sumo Logic](https://scaleengineer.com/companies/sumo-logic)
---
## Problem
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
## Graph Traversal to Find Connected Components
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.
**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).
**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.
### Explanation
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`.

```java
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);
            }
        }
    }
}
```
### 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`.

## Union-Find (Disjoint Set Union)
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.
**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).
**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.
### Explanation
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:
1.  **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.
2.  **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.

```java
class Solution {
    private int[] parent;

    // Find operation with path compression
    private int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]);
    }

    // Union operation (can be improved with union by size/rank)
    private void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
        }
    }

    public boolean equationsPossible(String[] equations) {
        parent = new int[26];
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }

        // 1. Process all '==' equations
        for (String eq : equations) {
            if (eq.charAt(1) == '=') {
                int u = eq.charAt(0) - 'a';
                int v = eq.charAt(3) - 'a';
                union(u, v);
            }
        }

        // 2. Process all '!=' equations
        for (String eq : equations) {
            if (eq.charAt(1) == '!') {
                int u = eq.charAt(0) - 'a';
                int v = eq.charAt(3) - 'a';
                if (find(u) == find(v)) {
                    return false; // Contradiction
                }
            }
        }

        return true;
    }
}
```
### 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`.

# Solutions
### Java

```java
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];
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> p;
  bool equationsPossible(vector<string> &equations) {
    p.resize(26);
    for (int i = 0; i < 26; ++i)
      p[i] = i;
    for (auto &e : equations) {
      int a = e[0] - 'a', b = e[3] - 'a';
      if (e[1] == '=')
        p[find(a)] = find(b);
    }
    for (auto &e : equations) {
      int a = e[0] - 'a', b = e[3] - 'a';
      if (e[1] == '!' && find(a) == find(b))
        return false;
    }
    return true;
  }
  int find(int x) {
    if (p[x] != x)
      p[x] = find(p[x]);
    return p[x];
  }
};

```

### Python

```python
class Solution:
    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

```