Determine if a list of equations (like "a==b", "b!=c") can all be satisfied simultaneously.
Input: equations=["a==b","b!=c","c==a"] → Output: false
Input: equations=["c==c","b==d","x!=z"] → Output: true
Two passes: first union all "==" pairs; then check "!=" pairs for conflicts.
- First pass: union all a==b pairs
- Second pass: for each a!=b pair: if find(a)==find(b) return false (contradiction)
- Return true if no contradictions
public boolean equationsPossible(String[] equations) {
int[] parent = new int[26];
for (int i = 0; i < 26; i++) parent[i] = i;
for (String eq : equations)
if (eq.charAt(1) == '=')
parent[find(parent, eq.charAt(0)-'a')] = find(parent, eq.charAt(3)-'a');
for (String eq : equations)
if (eq.charAt(1) == '!' && find(parent, eq.charAt(0)-'a') == find(parent, eq.charAt(3)-'a'))
return false;
return true;
}
private int find(int[] parent, int x) {
return parent[x] == x ? x : (parent[x] = find(parent, parent[x]));
}
- Time Complexity: O(n * alpha(26))
- Space Complexity: O(1)