990. Satisfiability of Equality Equations

 

Satisfiability of Equality Equations

Problem Description

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 <= 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.

Idea:

• We iterate the equations twice, the first time is to union the elements and build the map, so we only care about the "==". 
• The Second time is to check if there's any conflict, so we only need to take care of "!=".

Let's Code It!

/**
 * @param {string[]} equations
 * @return {boolean}
 */
var equationsPossible = function(equations) {
    const map = new Map(),
          find = item => {
              map.set(item, map.get(item) || item);
              return item === map.get(item) ? item : find(map.get(item));
          };
    
    equations.forEach(([a, eq, , b]) => {
        if (eq === '=') {
            map.set(find(a), find(b));
        }
    });
    
    let complies = true;
    equations.forEach(([a, eq, , b]) => {
        if (eq === '!') {
            if (find(a) === find(b)) complies = false;
        }
    });
    
    return complies;
}

Idea: (Another way to write a solution)

First of all, we create the template for union-find DS which is two standard functions union and find and underlying hashmap that maps letters to letters and represents groups to which each letter should belong according to equality equations.

We do two passes, one for preprocessing letters to add them in the hashmap and also unite them to the same groups according to equality equations. And the second pass to check contradictions which is some two letters belong to the same group but an equation requires them to be different.

Let's Code It!

var equationsPossible = function(equations) {
	let p = new Map()
	
    // preprocess: create map and unite similar
	for (let eq of equations) {
	    let x = eq[0],
		    y = eq[3],
		    cond = eq[1]

		// add newly met letters to the hashmap and assign them to own groups
        if (!p.has(x)) p.set(x, x)
        if (!p.has(y)) p.set(y, y)

        if (cond === '=') 
            union(x, y)
    }
    
    // check for contradictions
    for (let eq of equations) {
	    let x = eq[0],
		    y = eq[3],
		    cond = eq[1]
        
		// condition is `not equal` but variables have to be the same according to previous preprocessing
		if (cond === '!' && find(x) === find(y))
            return false
    }
    
    function union(x, y) {
        p.set(find(x), find(y))
    }

    function find(letter) {
        while (p.get(letter) !== letter) {
            p.set(letter, p.get(p.get(letter))) // compress path
            letter = p.get(letter)
        }

        return letter
    } 
    return true 
}

Complexity 

Time Complexity
For two iterations O(n).

Space Complexity
We are using Map as a data structure to facilitate our computation, therefore, the space complexity should also be O(n), right? Wrong!

Resources:

https://github.com/PraveenMistry/leetCode

https://medium.com/@praveenmistry

Conclusion

That’s all folks! In this post, we solved LeetCode problem #990. Satisfiability of Equality Equations

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!