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.

Examples

Example 1:

1
2
3
4

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:

1
2
3

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

Method 1 - Using Hashmap for Storing Relations ❌

The code provided below will not work for the example ["a==b", "b!=c", "c==a"].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public boolean equationsPossible(String[] equations) {
	Map<Character, Set<Character>> eqm = new HashMap<>();
	Map<Character, Set<Character>> neqm = new HashMap<>();
	for (String equation: equations) {
		char x = equation.charAt(0);
		char y = equation.charAt(3);
		
		Map<Character, Set<Character>> mapToCheck = new HashMap<>();
		Map<Character, Set<Character>> mapToAdd = new HashMap<>();
		if (equation.charAt(1) == '=') {
			mapToCheck = neqm;
			mapToAdd = eqm;
		}else {
			mapToCheck = eqm;
			mapToAdd = neqm;
		}
		
		if (mapToCheck.containsKey(x) && mapToCheck.get(x).contains(y)) {
				return false;
		}
		mapToAdd.putIfAbsent(x, new HashSet<>());
		mapToAdd.putIfAbsent(y, new HashSet<>());
		mapToAdd.get(x).add(y);
		mapToAdd.get(y).add(x);
	}
	
	return true;
}

Complexity

  • Time: O(n)
  • Space: O(n)

Method 2 - Using Union Find

Considering the example ["a==b", "b!=c", "c==a"], a and b belong to the same set. However, b and c should not be in the same set. Therefore, when trying to place c and a in the same set, it causes a contradiction since b and c cannot coexist in the same set. We can address this using code similar to Disjoint Set - Weighted Union Implementation.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

class Solution {
	int[] parent = new int[26];
	int[] size = new int[26];
	public boolean equationsPossible(String[] equations) {
		for (int i = 0; i<26; i++) {
			size[i] = 1;
			parent[i] = i;
		}

		for (String s: equations) {
			if (s.charAt(1) == '=') {
				int a = s.charAt(0) - 'a';
				int b = s.charAt(3) - 'a';
				union(a, b);
			}
		}
		for (String s: equations) {
			if (s.charAt(1) == '!') {
				int a = s.charAt(0) - 'a';
				int b = s.charAt(3) - 'a';
				if (isConnected(a, b)) {
					return false;
				}
			}
		}
		return true;
	}
	public void union(int a, int b) {
		int roota = find(a);
		int rootb = find(b);
		if (roota == rootb) {
			return;
		}
		if (size[roota] >= size[rootb]) {
			parent[rootb] = roota;
			size[roota] += size[rootb];
		} else {
			parent[roota] = rootb;
			size[rootb] += size[roota];
		}
	}
	public int find(int a) {
		while (parent[a] != a) {
			a = parent[a];
		}
		return a;
	}
	public boolean isConnected(int a, int b) {
		int roota = find(a);
		int rootb = find(b);
		if (roota == rootb) {
			return true;
		}
		return false;
	}

}

Complexity

  • Time: O(N)
  • Space: O(N)