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 <= 500equations[i].length == 4equations[i][0] is a lowercase letter.equations[i][1] is either '=' or '!'.equations[i][2] is '='.equations[i][3] is a lowercase letter.This approach uses the Union-Find data structure to manage connectivity between variables. The core idea is to group variables that are known to be equal using '=='. After processing all such equations, we then check the '!=' equations to ensure that connected variables (i.e., variables that are in the same component) are not incorrectly marked as not equal.
Steps:
The solution uses two functions find and unionSet to implement the Union-Find operations. Each variable is initially its own parent. For each '==' equation, the unionSet function connects the two variables. For each '!=' equation, the find function checks if both variables are connected, returning false if they are, because they shouldn't be connected. The program finally returns true if no such pairs exist.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * α(n)) where n is the number of equations, and α is the inverse Ackermann function.
Space Complexity: O(1) as we are using a fixed-size array of 26 characters.
Another method is to visualize the problem as a graph and determine if the '==' relations create valid partitions without violating '!=' conditions. This is managed using a BFS approach.
Steps:
This C solution constructs an undirected graph for the equality constraints and checks inequality constraints using a BFS traversal. If any graph component contains both nodes linked by a '!=' relation, it returns false. The operation checks conflicts and resets visitation states for independent inequality checks.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the number of equations as each one is processed once during graph building and inequality checks.
Space Complexity: O(1) as it uses a fixed-size 26x26 adjacency matrix.
| Approach | Complexity |
|---|---|
| Union-Find Data Structure | Time Complexity: O(n * α(n)) where n is the number of equations, and α is the inverse Ackermann function. |
| Graph Connectivity with BFS | Time Complexity: O(n) where n is the number of equations as each one is processed once during graph building and inequality checks. |
Satisfiability of Equality Equations - (GOOGLE) | Graph Concepts & Qns - 21 | Explanation+Coding • codestorywithMIK • 11,812 views views
Watch 9 more video solutions →Practice Satisfiability of Equality Equations with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor