Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 <= 500equations[i].length == 4equations[i][0] is a lowercase letter.equations[i][1] is either '=' or '!'.equations[i][2] is '='.equations[i][3] is a lowercase letter.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Union-Find
["a==b","b!=a"]
["b==a","a==b"]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #990: Satisfiability of Equality Equations
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];
}
}
// Accepted solution for LeetCode #990: Satisfiability of Equality Equations
func equationsPossible(equations []string) bool {
p := make([]int, 26)
for i := 1; i < 26; i++ {
p[i] = i
}
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
for _, e := range equations {
a, b := int(e[0]-'a'), int(e[3]-'a')
if e[1] == '=' {
p[find(a)] = find(b)
}
}
for _, e := range equations {
a, b := int(e[0]-'a'), int(e[3]-'a')
if e[1] == '!' && find(a) == find(b) {
return false
}
}
return true
}
# Accepted solution for LeetCode #990: Satisfiability of Equality Equations
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
// Accepted solution for LeetCode #990: Satisfiability of Equality Equations
struct Solution;
struct UnionFind {
parent: Vec<usize>,
n: usize,
}
impl UnionFind {
fn new(n: usize) -> Self {
let parent = (0..n).collect();
UnionFind { parent, n }
}
fn find(&mut self, i: usize) -> usize {
let j = self.parent[i];
if i == j {
j
} else {
let k = self.find(j);
self.parent[i] = k;
k
}
}
fn union(&mut self, i: usize, j: usize) {
let i = self.find(i);
let j = self.find(j);
if i != j {
self.parent[i] = j;
self.n -= 1;
}
}
}
impl Solution {
fn equations_possible(equations: Vec<String>) -> bool {
let mut uf = UnionFind::new(26);
let mut pairs: Vec<(usize, usize)> = vec![];
for equation in equations {
let s: Vec<char> = equation.chars().collect();
let i = (s[0] as u8 - b'a') as usize;
let j = (s[3] as u8 - b'a') as usize;
if s[1] == '=' {
uf.union(i, j);
} else {
pairs.push((i, j));
}
}
for pair in pairs {
let i = pair.0;
let j = pair.1;
if uf.find(i) == uf.find(j) {
return false;
}
}
true
}
}
#[test]
fn test() {
let equations = vec_string!["a==b", "b!=a"];
let res = false;
assert_eq!(Solution::equations_possible(equations), res);
let equations = vec_string!["b==a", "a==b"];
let res = true;
assert_eq!(Solution::equations_possible(equations), res);
let equations = vec_string!["a==b", "b==c", "a==c"];
let res = true;
assert_eq!(Solution::equations_possible(equations), res);
let equations = vec_string!["a==b", "b!=c", "c==a"];
let res = false;
assert_eq!(Solution::equations_possible(equations), res);
let equations = vec_string!["c==c", "b==d", "x!=z"];
let res = true;
assert_eq!(Solution::equations_possible(equations), res);
}
// Accepted solution for LeetCode #990: Satisfiability of Equality Equations
class UnionFind {
private parent: number[];
constructor() {
this.parent = Array.from({ length: 26 }).map((_, i) => i);
}
find(index: number) {
if (this.parent[index] === index) {
return index;
}
this.parent[index] = this.find(this.parent[index]);
return this.parent[index];
}
union(index1: number, index2: number) {
this.parent[this.find(index1)] = this.find(index2);
}
}
function equationsPossible(equations: string[]): boolean {
const uf = new UnionFind();
for (const [a, s, _, b] of equations) {
if (s === '=') {
const index1 = a.charCodeAt(0) - 'a'.charCodeAt(0);
const index2 = b.charCodeAt(0) - 'a'.charCodeAt(0);
uf.union(index1, index2);
}
}
for (const [a, s, _, b] of equations) {
if (s === '!') {
const index1 = a.charCodeAt(0) - 'a'.charCodeAt(0);
const index2 = b.charCodeAt(0) - 'a'.charCodeAt(0);
if (uf.find(index1) === uf.find(index2)) {
return false;
}
}
}
return true;
}
Use this to step through a reusable interview workflow for this problem.
Track components with a list or adjacency matrix. Each union operation may need to update all n elements’ component labels, giving O(n) per union. For n union operations total: O(n²). Find is O(1) with direct lookup, but union dominates.
With path compression and union by rank, each find/union operation takes O(α(n)) amortized time, where α is the inverse Ackermann function — effectively constant. Space is O(n) for the parent and rank arrays. For m operations on n elements: O(m × α(n)) total.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.