Hello, reader 👋🏽 ! Welcome to day 81 of the series on Problem Solving. Through this series, I aim to pick up at least one question every day and share my approach to solving it.
Today, I will be picking up LeetCode's daily challenge problem: 886. Possible Bipartition.
🤔 Problem Statement
We want to split a group of
npeople (labelled from1ton) into two groups of any size.Each person may dislike some other people, and they should not go into the same group.
Given the integer
nand the arraydislikeswheredislikes[i] = [ai, bi]indicates that the person labelledaidoes not as like the person labelledbi, returntrueif it is possible to split everyone into two groups in this way.E.g.:
dislikes = [[1,2],[1,3],[2,4]] => true dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]] => false
💬 Thought Process - Is Graph Bipartite: BFS
To check if we can split nodes into two different groups, we can check if the graph is a bipartite graph.
A bipartite graph is one where the nodes can be coloured with two colours such that no two neighbouring nodes share the same colour.
If we are able to successfully colour nodes with say
c1andc2, then that means that we have split the graph into two groups: one group with nodes of colourc1and the other with nodes of colourc2.To do this, we can do a normal BFS traversal and instead of a visited set, we can maintain a colours array where we use either
1or2as colour.At every node, if the colour is
1, then we try to paint all the neighbouring nodes with colour2.- Or vice versa, if the colour of the current node is
2, we will try to paint all the neighbouring nodes with1.
- Or vice versa, if the colour of the current node is
The violation if the graph cannot be bipartite happens when any of the nodes a node and its immediate neighbour both share the same colour.
In that case, it would indicate that the nodes of the graph cannot be split into two groups and we return false.
One point to note in this problem is that the graph could be disconnected. Hence we need to check if every component is bipartite or not.
If any one component is not bipartite, then we return false.
👩🏽💻 Solution - Is Graph Bipartite: BFS
- Below is the code for the approach for solving this problem by finding if the graph is bipartite or not using BFS traversal.
class Solution {
private List<List<Integer>> adj;
private int[] colors;
public boolean possibleBipartition(int n, int[][] dislikes) {
adj = new ArrayList();
for(int i = 0; i<=n; i++) {
adj.add(new ArrayList());
}
generateAdjList(dislikes);
colors = new int[n+1];
for(int i = 1; i<=n; i++) {
if(colors[i] == 0) {
boolean isBipartite = traverseNodes(n, i);
if(!isBipartite) return false;
}
}
return true;
}
private void generateAdjList(int[][] dislikes) {
for(int[] dislike: dislikes) {
int u = dislike[0], v = dislike[1];
adj.get(u).add(v);
adj.get(v).add(u);
}
}
private boolean traverseNodes(int n, int source) {
Queue<Integer> nodes = new LinkedList();
colors[source] = 1;
nodes.add(source);
while(!nodes.isEmpty()) {
int currNode = nodes.poll();
int currColor = colors[currNode];
for(int nextNode: adj.get(currNode)) {
if(colors[nextNode] == 0) {
colors[nextNode] = (currColor == 1) ? 2 : 1;
nodes.add(nextNode);
}
else if(colors[nextNode] == currColor) {
return false;
}
}
}
return true;
}
}
Time Complexity: O(v + e)
- e = number of edges
- v = number of nodes
Space Complexity: O(v + e)
- e = number of edges
- v = number of nodes
💬 Thought Process - Is Graph Bipartite: DFS
The problem can also be solved using the DFS traversal approach where we recursively traverse the neighbours of a node in depth.
The approach would be the exact same, but here we would make use of recursive calls rather than having an implicit data structure that keeps track of nodes to be processed.
At every DFS call, we pass the colour of the previous nodes and then paint the neighbour using the opposite colour.
If we find the violation, we immediately stop the DFS calls and return false.
👩🏽💻 Solution - DFS
- Below is the code for the approach for solving this problem by checking if the graph is bipartite using DFS traversal.
class Solution {
private List<List<Integer>> adj;
private int[] colors;
public boolean possibleBipartition(int n, int[][] dislikes) {
adj = new ArrayList();
for(int i = 0; i<=n; i++) {
adj.add(new ArrayList());
}
generateAdjList(dislikes);
colors = new int[n+1];
for(int i = 1; i<=n; i++) {
if(colors[i] == 0) {
boolean isBipartite = traverseNodes(n, i, 1);
if(!isBipartite) return false;
}
}
return true;
}
private void generateAdjList(int[][] dislikes) {
for(int[] dislike: dislikes) {
int u = dislike[0], v = dislike[1];
adj.get(u).add(v);
adj.get(v).add(u);
}
}
private boolean traverseNodes(int n, int currNode, int prevColor) {
int currColor = (prevColor == 1) ? 2 : 1;
colors[currNode] = currColor;
for(int nextNode: adj.get(currNode)) {
if(colors[nextNode] == 0) {
boolean isBipartite = traverseNodes(n, nextNode,
currColor);
if(!isBipartite) return false;
}
else if(colors[nextNode] == currColor) {
return false;
}
}
return true;
}
}
Time Complexity: O(v + e)
- e = number of edges
- v = number of nodes
Space Complexity: O(v + e)
- e = number of edges
- v = number of nodes
💬 Thought Process - Union Find
In this problem, we will use union find to form sets of nodes into two different groups.
We will form an adjacency list where we will store a list of all the nodes which a node
idislikes.Then we will try to form a union of all the nodes such that if nodes
aandbare disliked by noden, thenaandbwould form a union.That is, we will form a union with the first disliked node of
iand all the other disliked nodes of the nodei.But before we build this union, we will check if two nodes belong to the same group using the
find()which returns the parent of a node.- That is, If the parent of the nodes
iandjare the same, but nodesiandjbelong to the same group with one of them disliking the other node, we return false;
- That is, If the parent of the nodes
If we manage to form successfully form unions with all nodes, we return true.
👩🏽💻 Solution - Union Find
- Below is the code for the approach for solving this using Union Find.
class UnionFind {
int[] parent, rank;
int n;
UnionFind(int n) {
this.n = n;
parent = new int[n+1];
rank = new int[n+1];
for(int i = 0; i<=n; i++) {
parent[i] = i;
}
for(int i = 0; i<=n; i++) {
rank[i] = 1;
}
}
public int find(int u) {
if(parent[u] == u) return u;
return parent[u] = find(parent[u]);
}
public void union(int u, int v) {
int parU = find(u);
int parV = find(v);
if(parU == parV) {
return;
}
if(rank[parU] < rank[parV]) {
parent[parU] = parV;
}
else if(rank[parV] < rank[parU]) {
parent[parV] = parU;
}
else {
parent[parV] = parU;
rank[parU]++;
}
}
}
class Solution {
private List<List<Integer>> adj;
private int[] colors;
public boolean possibleBipartition(int n, int[][] dislikes) {
adj = new ArrayList();
for(int i = 0; i<=n; i++) {
adj.add(new ArrayList());
}
generateAdjList(dislikes);
UnionFind uf = new UnionFind(n);
for(int node = 1; node<=n; node++) {
for(int neighbor: adj.get(node)) {
if(uf.find(node) == uf.find(neighbor)) {
return false;
}
uf.union(adj.get(node).get(0), neighbor);
}
}
System.out.println(Arrays.toString(uf.parent));
return true;
}
private void generateAdjList(int[][] dislikes) {
for(int[] dislike: dislikes) {
int u = dislike[0], v = dislike[1];
adj.get(u).add(v);
adj.get(v).add(u);
}
}
}
Time Complexity: O(v + e)
- e = number of edges
- v = number of nodes
Space Complexity: O(v + e)
- e = number of edges
- v = number of nodes
- You can find the link to the GitHub repo for this question here: 886. Possible Bipartition.
Conclusion
That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!
Thank you for reading!