Satisfiability of Equality Equations - Practice Coding Problems

Satisfiability of Equality Equations - 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.

Input & Output

Example 1 — Basic Valid Case

$ Input: equations = ["a==b","b!=c"]

› Output: true

💡 Note: Variables a and b must be equal, and b must not equal c. We can assign a=b=0 and c=1, satisfying both equations.

Example 2 — Contradiction

$ Input: equations = ["a==b","b==c","a!=c"]

› Output: false

💡 Note: If a==b and b==c, then a==c by transitivity. But we also have a!=c, which creates a contradiction.

Example 3 — Self Reference

$ Input: equations = ["a!=a"]

› Output: false

💡 Note: A variable cannot be not equal to itself, so this equation is impossible to satisfy.

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array of equality/inequality equations between variables

Process

Group equal variables and check for conflicts

Output

Boolean indicating if all equations can be satisfied

Key Takeaway

🎯 Key Insight: Group equal variables first, then verify inequalities don't connect variables within the same group

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is to recognize this as a graph connectivity problem. Use Union-Find to group variables that must be equal, then verify inequalities don't create contradictions. Best approach is Union-Find with Time: O(n × α(n)), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Union-Find (Disjoint Set)	O(n × α(n))	O(1)	Use Union-Find to group equal variables, then check if inequalities violate groups
Brute Force - Try All Assignments	O(k^n × m)	O(n)	Try all possible integer assignments to variables and check if equations are satisfied

Union-Find (Disjoint Set) — Algorithm Steps

Initialize Union-Find structure
Process == equations to union variables
Check != equations don't connect variables in same group

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Equalities

Union variables that must be equal

Check Inequalities

Verify no inequality connects same group

Result

Return true if no conflicts found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int parent[26];

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unionSets(int x, int y) {
    int px = find(x);
    int py = find(y);
    if (px != py) {
        parent[px] = py;
    }
}

bool solution(char equations[][5], int eqCount) {
    // Initialize Union-Find
    for (int i = 0; i < 26; i++) {
        parent[i] = i;
    }
    
    // Process equality equations first
    for (int i = 0; i < eqCount; i++) {
        if (equations[i][1] == '=' && equations[i][2] == '=') {
            int x = equations[i][0] - 'a';
            int y = equations[i][3] - 'a';
            unionSets(x, y);
        }
    }
    
    // Check inequality equations
    for (int i = 0; i < eqCount; i++) {
        if (equations[i][1] == '!' && equations[i][2] == '=') {
            int x = equations[i][0] - 'a';
            int y = equations[i][3] - 'a';
            if (find(x) == find(y)) {
                return false;
            }
        }
    }
    
    return true;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char equations[100][5];
    int eqCount = 0;
    
    char *start = strchr(line, '"');
    while (start) {
        start++;
        char *end = strchr(start, '"');
        if (end) {
            strncpy(equations[eqCount], start, 4);
            equations[eqCount][4] = '\0';
            eqCount++;
        }
        start = strchr(end + 1, '"');
    }
    
    bool result = solution(equations, eqCount);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × α(n))

Each equation requires Union-Find operations with inverse Ackermann factor

✓ Linear Growth

Space Complexity

O(1)

Only uses fixed-size parent array for 26 lowercase letters

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Union-Find (Disjoint Set) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler