1032. Satisfiability Of Equality Equations¶

Difficulty: Medium

1032. Satisfiability of Equality Equations

Medium

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: "x_i==y_i" or "x_i!=y_i".Here, x_i and y_i 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.

Solution¶

class Solution {
    static class DSU {
        private int parent[];
        private int size[];
        public DSU(int n) {
            parent = new int[n + 1];
            size = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        public int find_parent(int u) {
            if (parent[u] == u) return parent[u] = u;
            return parent[u] = find_parent(parent[u]);
        }
        public void unite(int u , int v) {
            u = find_parent(u);
            v = find_parent(v);
            if (u == v) return;
            if (size[v] > size[u]) {
                int temp = u;
                u = v;
                v = temp;
            }
            parent[v] = u;
            size[u] += size[v];
        }
    }
    public boolean equationsPossible(String[] equations) {
        int n = equations.length;
        DSU dsu = new DSU(30);
        for (int i = 0; i < n; i++) {
            int u = equations[i].charAt(0) - 'a';
            int v = equations[i].charAt(3) - 'a';
            char current = equations[i].charAt(1);
            if (current == '=') dsu.unite(u, v);
        }
        for (int i = 0; i < n; i++) {
            int u = equations[i].charAt(0) - 'a';
            int v = equations[i].charAt(3) - 'a';
            char current = equations[i].charAt(1);
            if (current == '!') {
                u = dsu.find_parent(u);
                v = dsu.find_parent(v);
                if (u == v) return false;
            }
        }
        return true;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here