algoadvance

Leetcode 886. Possible Bipartition

Problem Statement

Given a set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size. Each person may dislike some other people, and they should not be in the same group. Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group. Return true if and only if it is possible to split everyone into two groups in this way.

Clarifying Questions

  1. What is the range of N?
    • 1 <= N <= 2000
  2. What about the size of dislikes array?
    • 1 <= dislikes.length <= 10000
  3. Can there be multiple dislikes for the same pair?
    • No, each pair is unique.
  4. Are there any cases where there are no dislikes?
    • Yes, if dislikes is empty, then it is trivially possible to split into two groups.

Strategy

The idea is to check if the graph (formed by the dislikes) is bipartite. A graph is bipartite if we can color it using two colors such that no two adjacent nodes have the same color. We can use a Breadth-First Search (BFS) approach or Depth-First Search (DFS) approach to try to color the graph.

If we are able to color the graph using just two colors, then it is possible to partition the people into two groups according to the dislikes constraints.

Code

Here’s the BFS approach in C++:

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        vector<vector<int>> graph(N + 1);
        for (const auto &edge : dislikes) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        vector<int> color(N + 1, 0); // 0: uncolored, 1: color1, -1: color2
        
        for (int i = 1; i <= N; ++i) {
            if (color[i] == 0) {
                queue<int> q;
                q.push(i);
                color[i] = 1; // Assign the first color
                
                while (!q.empty()) {
                    int current = q.front();
                    q.pop();
                    
                    for (int neighbor : graph[current]) {
                        if (color[neighbor] == 0) { // If not colored, color with the opposite color
                            color[neighbor] = -color[current];
                            q.push(neighbor);
                        } else if (color[neighbor] == color[current]) { // If the neighbor has the same color, the graph is not bipartite
                            return false;
                        }
                    }
                }
            }
        }
        
        return true;
    }
};

Time Complexity

Thus, the overall time complexity is O(N + dislikes.length). This should be efficient given the constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI