Crack the Backend

Problem Statement

You are given an array of strings equations where each is either "a==b" or "a!=b" (a, b are lowercase letters). Return true if and only if it is possible to assign integers to variables so that all equations are satisfied.

Key Observations

Union Find: First, union every pair (a, b) for all "a==b" equations — so variables that must be equal are in the same set. Then for every "a!=b" equation: if find(a) == find(b), we have a contradiction (we already forced a and b equal). Return false. If no such contradiction, return true.

Approach

High-level: UF on 26 letters. For each "a==b" union(a-'a', b-'a'). For each "a!=b" if find(a)==find(b) return false. Return true.

Steps: int[] parent = new int[26]; for (i=0;i<26;i++) parent[i]=i; for (String eq : equations) if (eq.charAt(1)=='=') union(eq.charAt(0)-'a', eq.charAt(3)-'a'); for (String eq : equations) if (eq.charAt(1)=='!' && find(eq.charAt(0)-'a')==find(eq.charAt(3)-'a')) return false; return true;

Implementation

Java

int[] parent = new int[26];
int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); }

public boolean equationsPossible(String[] equations) {

    for (int i = 0; i < 26; i++) {
        parent[i] = i;
    }

    for (String e : equations)
    if (e.charAt(1) == '=') {
        parent[find(e.charAt(0)-'a')] = find(e.charAt(3)-'a');
    }

    for (String e : equations)
    if (e.charAt(1) == '!' && find(e.charAt(0)-'a') == find(e.charAt(3)-'a')) {
        return false;
    }

    return true;
}

Test Cases

Example 1

Input

["a==b","b!=a"]

Expected

false

Explanation

Conflict.

Complexity Analysis

Time: O(n α(n)) ≈ O(n).
Space: O(n).

Follow-ups

Path compression + rank for optimal UF.