Possible Bipartition LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple Bloomberg ByteDance Coupang Google Microsoft
tiktokViews 2185

Problem Statement

Possible Bipartition LeetCode Solution – We want to split a group of n people (labeled from 1 to n) 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 n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.

Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4] and group2 [2,3].

Explanation

The question asks us to divide given people into two groups such that no two people in the same group dislike each other.

For ease of understanding, we can represent this problem as a graph, with people being the vertices and dislike-pairs being the edges of this graph.

We have to find out if the vertices can be divided into two sets such that there aren’t any edges between vertices of the same set. A graph satisfying this condition is called a bipartite graph.

We try to color the two sets of vertices, with RED and BLUE colors. In a bipartite graph, a RED vertex must be connected only with BLUE vertices and a BLUE vertex must be connected only with RED vertices. In other words, there must NOT be an edge connecting two vertices of the same color. Such an edge will be a conflict edge.

The presence of conflict edges indicates that bipartition is NOT possible.

The graph may consist of many connected components. For each connected component, we run our BFS algorithm to find conflict edges, if any. For each component, we start by coloring one vertex RED, and all its neighbors BLUE. Then we visit the BLUE vertices and color all their neighbors as RED, and so on. During this process, if we come across any RED-RED edge or BLUE-BLUE edge, we have found a conflict edge and we immediately return false, as bipartition will not be possible.

If no conflict edges are found at the end of the algorithm, it means bipartition is possible, hence we return true.

Possible Bipartition LeetCode Solution

Code

C++ Code For Possible Bipartition

#define WHITE 0
#define RED 1
#define BLUE 2
class Solution {
public:
    bool possibleBipartition(int N, vector<vector<int>> &edges) 
    {
        vector<vector<int>> adj(N + 1); 
        vector<int> color(N + 1, WHITE); 
        vector<bool> explored(N + 1, false); 
        for (auto &edge: edges)
        {
            int u = edge[0];
            int v = edge[1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
      
        queue<int> q;
        
        for (int i = 1; i <= N; ++i)
        {
            if (!explored[i])
            {
                color[i] = RED;
                q.push(i);
                
                // perform BFS from vertex i
                while (!q.empty())
                {
                    int u = q.front();
                    q.pop();
                    
                    // check if u is already explored 
                    if (explored[u])
                    {
                        continue;
                    }
                    
                    explored[u] = true;
                    
                    // for each neighbor of u, execute this loop
                    for (auto v: adj[u])
                    {
                        if (color[v] == color[u])
                        {
                            return false;
                        }
                        
                        // we color v with the opposite color of u
                        if (color[u] == RED)
                        {
                            color[v] = BLUE;
                        }
                        else 
                        {
                            color[v] = RED;
                        }
                        
                        q.push(v);
                    }
                }
            }
        }
        return true;
    }
};

Python Code for Possible Bipartition

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        self.graph = collections.defaultdict(list)
        group_mapping = {}
        for (u, v) in dislikes:                   # Create graph
            self.graph[u].append(v)
            self.graph[v].append(u)
        
        visited = set()
        for i in range(1, N + 1):                 # Iterate each node
            if i in visited: continue             # No need to revisit, since it's a non-directed graph
            stack = [(i, 0)]                      # Use stack for BFS
            while stack:                          # You can also use a deque instead of 2 while loop on stack
                tmp_stack = []
                while stack:                      # exhaust current stack before go to next layer (BFS)
                    cur_node, group = stack.pop()
                    if cur_node in group_mapping and group != group_mapping[cur_node]:  # check if it's conflict
                        return False
                    if cur_node in visited: continue        # If visited and no conflict, continue to avoid dead loop
                    group_mapping[cur_node] = group         # Assign group for current node
                    visited.add(cur_node)
                    for child in self.graph[cur_node]:      # Assign contrary group for dislikes of current node
                        tmp_stack.append((child, not group))
                stack = tmp_stack            
        return True

Java Code For Possible Bipartiton

class Solution {
public boolean possibleBipartition(int N, int[][] dislikes) {
        int[] color = new int[N + 1];
        List<List<Integer>> adj = new ArrayList<>(N + 1);
        for(int i = 0; i <= N; i++) adj.add(new ArrayList<Integer>());
        for(int[] d : dislikes) {
            adj.get(d[0]).add(d[1]);
            adj.get(d[1]).add(d[0]);
        }
        
        for(int i = 1; i <= N; i++) {
            if(color[i] == 0) {
                color[i] = 1;
                Queue<Integer> q = new LinkedList<>();
                q.add(i);
                while(!q.isEmpty()) {
                    int cur = q.poll();
                    for(int nb : adj.get(cur)) {
                        if(color[nb] == 0) {
                            color[nb] = color[cur] == 1 ? 2 : 1;
                            q.add(nb);
                        } else {
                            if(color[nb] == color[cur]) return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

Complexity Analysis for Possible Bipartition LeetCode Solution

Time Complexity

O (N + E) since we take O(E) time to create an adjacency list and O (N) time to make a BFS traversal on it.

Space Complexity

O(N+E) since we store an adjacency list for the graph and also a visited array.

Reference: https://en.wikipedia.org/wiki/Bipartite_graph

Translate »