Possible Bipartition solution and explanation
Google
9 more videos on this problem
Possible Bipartition | Bipartite graph | Graph coloring | Leetcode #886Techdose · 23:34 · 55K views
花花酱 LeetCode 886. Possible Bipartition - 刷题找工作 EP217Hua Hua · 13:03 · 8K views
Possible Bipartition | leetcode 886 | HindiCodebix · 17:39 · 3K views
Leetcode - Possible Bipartition (Python)Timothy H Chang · 9:16 · 3K views
LeetCode 886. Possible Bipartition Explanation and Solutionhappygirlzt · 7:58 · 2K views
Daily Leetcode #995: Dec 21, 2022 - 886. Possible BipartitionProgramming Live with Larry · 16:16 · 816 views
LeetCode 886 Possible BipartitionAshish Kumar · 12:45 · 808 views
Possible Bipartition - Bipartite Graph - DFS - PythonCheatCode Ninja · 7:38 · 654 views
Possible Bipartition | Leetcode Day: 27 | graph | May challenge | question. #886Khushboo Goel · 3:39 · 450 views
Leetcode 886: Possible BipartitionAlgorithms Casts · 12:16 · 174 views
The problem
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.
Example 1:
Input: n = 4, dislikes = [[1,2],[1,3],[2,4]] Output: true Explanation: The first group has [1,4], and the second group has [2,3].
Example 2:
Input: n = 3, dislikes = [[1,2],[1,3],[2,3]] Output: false Explanation: We need at least 3 groups to divide them. We cannot put them in two groups.
Constraints:
1 <= n <= 20000 <= dislikes.length <= 104dislikes[i].length == 21 <= ai < bi <= n- All the pairs of
dislikesare unique.
Approach overview
Problem Overview: You are given n people and a list of dislike pairs. Each pair means those two people cannot be in the same group. The task is to check whether you can split everyone into two groups so that no pair of people who dislike each other end up in the same group.
The structure formed by dislikes is a graph where each person is a node and every dislike pair is an undirected edge. The problem reduces to checking whether this graph is bipartite. A graph is bipartite if its nodes can be colored using two colors such that no adjacent nodes share the same color.
Approach 1: Graph Coloring Using BFS (O(n + m) time, O(n + m) space)
Build an adjacency list from the dislikes array so you can quickly access all neighbors of a person. Maintain a color array where each node is assigned either 1 or -1. Iterate through all nodes because the graph may have multiple disconnected components. For every uncolored node, start a Breadth-First Search. Assign the starting node a color, then push it into a queue. While processing the queue, give each neighbor the opposite color. If you encounter a neighbor that already has the same color as the current node, the graph cannot be bipartite, so the partition is impossible. BFS works well here because it explores level by level and naturally alternates colors across edges.
Approach 2: Graph Coloring Using DFS (O(n + m) time, O(n + m) space)
The same bipartite check can be implemented using Depth-First Search. After constructing the adjacency list, recursively traverse the graph and assign alternating colors to neighbors. Each DFS call colors the current node and then explores all adjacent nodes. If a neighbor already has a conflicting color, you immediately return false. DFS tends to produce shorter code because the recursion naturally handles traversal, while BFS uses an explicit queue. Both methods rely on the same underlying graph traversal idea and produce identical time complexity.
In both solutions, the key insight is that dislike relationships form edges in a graph, and the two groups correspond to the two colors of a bipartite graph. The algorithm simply attempts to color the graph while respecting those constraints.
Recommended for interviews: The BFS graph-coloring solution is commonly expected because it clearly demonstrates understanding of bipartite graphs and iterative traversal. DFS is equally correct and sometimes shorter to implement. Interviewers mainly look for the insight that this is a bipartite graph problem and that coloring during traversal detects conflicts in O(n + m) time.
Approach 1: Approach 1: Graph Coloring Using BFS
This approach uses a BFS traversal to determine if the graph is bipartite. A graph is bipartite if you can color it using two colors such that no two adjacent nodes have the same color. We'll represent people as nodes and dislikes as edges.
from collections import deque
def possible_bipartition(n, dislikes):
graph = [[] for _ in range(n + 1)]
for u, v in dislikes:
graph[u].append(v)
graph[v].append(u)
color = [0] * (n + 1)
def bfs(node):
queue = deque([node])
color[node] = 1
while queue:
current = queue.popleft()
for neighbor in graph[current]:
if color[neighbor] == 0:
color[neighbor] = -color[current]
queue.append(neighbor)
elif color[neighbor] == color[current]:
return False
return True
for i in range(1, n + 1):
if color[i] == 0:
if not bfs(i):
return False
return Trueimport java.util.*;
public class Solution {
public boolean possibleBipartition(int n, int[][] dislikes) {
List<Integer>[] graph = new List[n + 1];
for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
for (int[] edge : dislikes) {
graph[edge[0]].add(edge[1]);
graph[edge[1]].add(edge[0]);
}
int[] color = new int[n + 1];
Arrays.fill(color, 0);
for (int i = 1; i <= n; i++) {
if (color[i] == 0) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(i);
color[i] = 1;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : graph[node]) {
if (color[neighbor] == 0) {
color[neighbor] = -color[node];
queue.offer(neighbor);
} else if (color[neighbor] == color[node]) {
return false;
}
}
}
}
}
return true;
}
}#include <vector>
#include <queue>
using namespace std;
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
vector<vector<int>> graph(n + 1);
vector<int> color(n + 1, 0);
for (const auto& edge : dislikes) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
for (int i = 1; i <= n; ++i) {
if (!color[i]) {
queue<int> q;
q.push(i);
color[i] = 1;
while (!q.empty()) {
int node = q.front(); q.pop();
for (int neighbor : graph[node]) {
if (!color[neighbor]) {
color[neighbor] = -color[node];
q.push(neighbor);
} else if (color[neighbor] == color[node]) {
return false;
}
}
}
}
}
return true;
}const possibleBipartition = (n, dislikes) => {
const graph = Array.from({ length: n + 1 }, () => []);
for (const [u, v] of dislikes) {
graph[u].push(v);
graph[v].push(u);
}
const color = new Array(n + 1).fill(0);
const bfs = (start) => {
const queue = [start];
color[start] = 1;
while (queue.length > 0) {
const node = queue.shift();
for (const neighbor of graph[node]) {
if (color[neighbor] === 0) {
color[neighbor] = -color[node];
queue.push(neighbor);
} else if (color[neighbor] === color[node]) {
return false;
}
}
}
return true;
};
for (let i = 1; i <= n; i++) {
if (color[i] === 0) {
if (!bfs(i)) {
return false;
}
}
}
return true;
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXN 2001
int* graph[MAXN];
int graphSize[MAXN] = {0};
int color[MAXN];
bool bfs(int src) {
int queue[MAXN];
int front = 0, rear = 0;
queue[rear++] = src;
color[src] = 1;
while (front < rear) {
int node = queue[front++];
for (int i = 0; i < graphSize[node]; i++) {
int neighbor = graph[node][i];
if (color[neighbor] == 0) {
color[neighbor] = -color[node];
queue[rear++] = neighbor;
} else if (color[neighbor] == color[node]) {
return false;
}
}
}
return true;
}
bool possibleBipartition(int n, int** dislikes, int dislikesSize, int* dislikesColSize) {
for (int i = 1; i <= n; i++) {
graph[i] = (int*)malloc(sizeof(int) * (n + 1));
}
for (int i = 0; i < dislikesSize; i++) {
int u = dislikes[i][0];
int v = dislikes[i][1];
graph[u][graphSize[u]++] = v;
graph[v][graphSize[v]++] = u;
}
memset(color, 0, sizeof(color));
for (int i = 1; i <= n; i++) {
if (color[i] == 0) {
if (!bfs(i)) {
return false;
}
}
}
return true;
}using System;
using System.Collections.Generic;
public class Solution {
public bool PossibleBipartition(int n, int[][] dislikes) {
var graph = new List<int>[n + 1];
for (int i = 1; i <= n; i++)
graph[i] = new List<int>();
foreach (var edge in dislikes) {
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
var color = new int[n + 1];
bool Bfs(int start) {
var queue = new Queue<int>();
queue.Enqueue(start);
color[start] = 1;
while (queue.Count > 0) {
int node = queue.Dequeue();
foreach (int neighbor in graph[node]) {
if (color[neighbor] == 0) {
color[neighbor] = -color[node];
queue.Enqueue(neighbor);
} else if (color[neighbor] == color[node]) {
return false;
}
}
}
return true;
}
for (int i = 1; i <= n; i++) {
if (color[i] == 0) {
if (!Bfs(i)) {
return false;
}
}
}
return true;
}
}The Python solution adopts a BFS strategy with a deque (double-ended queue) for traversing and coloring the graph nodes. It checks for conflicting colors between adjacent nodes.
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges.
Space Complexity: O(V + E) due to the adjacency list and the BFS queue.
Approach 2: Approach 2: Graph Coloring Using DFS
This approach uses a DFS traversal to determine if the graph is bipartite. Similar to BFS, DFS attempts to color the graph using two colors to check if a valid bipartition is possible.
def possible_bipartition(n, dislikes):
graph = [[] for _ in range(n + 1)]
color = [0] * (n + 1)
for u, v in dislikes:
graph[u].append(v)
graph[v].append(u)
def dfs(node, c):
color[node] = c
for neighbor in graph[node]:
if color[neighbor] == 0:
if not dfs(neighbor, -c):
return False
elif color[neighbor] == color[node]:
return False
return True
for i in range(1, n + 1):
if color[i] == 0:
if not dfs(i, 1):
return False
return Trueimport java.util.*;
public class Solution {
public boolean possibleBipartition(int n, int[][] dislikes) {
List<Integer>[] graph = new List[n + 1];
for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
for (int[] edge : dislikes) {
graph[edge[0]].add(edge[1]);
graph[edge[1]].add(edge[0]);
}
int[] color = new int[n + 1];
Arrays.fill(color, 0);
for (int i = 1; i <= n; i++) {
if (color[i] == 0) {
if (!dfs(i, 1, graph, color)) return false;
}
}
return true;
}
private boolean dfs(int node, int c, List<Integer>[] graph, int[] color) {
color[node] = c;
for (int neighbor : graph[node]) {
if (color[neighbor] == 0) {
if (!dfs(neighbor, -c, graph, color)) return false;
} else if (color[neighbor] == c) {
return false;
}
}
return true;
}
}#include <vector>
using namespace std;
bool dfs(int node, int c, vector<vector<int>>& graph, vector<int>& color) {
color[node] = c;
for (int neighbor : graph[node]) {
if (!color[neighbor]) {
if (!dfs(neighbor, -c, graph, color)) return false;
} else if (color[neighbor] == color[node]) {
return false;
}
}
return true;
}
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
vector<vector<int>> graph(n + 1);
vector<int> color(n + 1, 0);
for (auto& edge : dislikes) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
for (int i = 1; i <= n; i++) {
if (!color[i] && !dfs(i, 1, graph, color)) {
return false;
}
}
return true;
}const possibleBipartition = (n, dislikes) => {
const graph = Array.from({ length: n + 1 }, () => []);
for (const [u, v] of dislikes) {
graph[u].push(v);
graph[v].push(u);
}
const color = new Array(n + 1).fill(0);
const dfs = (node, c) => {
color[node] = c;
for (const neighbor of graph[node]) {
if (color[neighbor] === 0) {
if (!dfs(neighbor, -c)) return false;
} else if (color[neighbor] === c) {
return false;
}
}
return true;
};
for (let i = 1; i <= n; i++) {
if (color[i] === 0) {
if (!dfs(i, 1)) {
return false;
}
}
}
return true;
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXN 2001
int* graph[MAXN];
int graphSize[MAXN] = {0};
int color[MAXN];
bool dfs(int node, int c) {
color[node] = c;
for (int i = 0; i < graphSize[node]; i++) {
int neighbor = graph[node][i];
if (color[neighbor] == 0) {
if (!dfs(neighbor, -c)) {
return false;
}
} else if (color[neighbor] == c) {
return false;
}
}
return true;
}
bool possibleBipartition(int n, int** dislikes, int dislikesSize, int* dislikesColSize) {
for (int i = 1; i <= n; i++) {
graph[i] = (int*)malloc(sizeof(int) * (n + 1));
}
for (int i = 0; i < dislikesSize; i++) {
int u = dislikes[i][0];
int v = dislikes[i][1];
graph[u][graphSize[u]++] = v;
graph[v][graphSize[v]++] = u;
}
memset(color, 0, sizeof(color));
for (int i = 1; i <= n; i++) {
if (color[i] == 0) {
if (!dfs(i, 1)) {
return false;
}
}
}
return true;
}using System;
using System.Collections.Generic;
public class Solution {
public bool PossibleBipartition(int n, int[][] dislikes) {
var graph = new List<int>[n + 1];
for (int i = 1; i <= n; i++)
graph[i] = new List<int>();
foreach (var edge in dislikes) {
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
var color = new int[n + 1];
bool Dfs(int node, int c) {
color[node] = c;
foreach (int neighbor in graph[node]) {
if (color[neighbor] == 0) {
if (!Dfs(neighbor, -c)) return false;
} else if (color[neighbor] == color[node]) {
return false;
}
}
return true;
}
for (int i = 1; i <= n; i++) {
if (color[i] == 0) {
if (!Dfs(i, 1)) {
return false;
}
}
}
return true;
}
}The Python solution employs a recursive DFS approach where each node is colored, and the function checks for conflicts in coloring among connected nodes.
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges.
Space Complexity: O(V + E) due to the adjacency list and recursion stack depth.
Approach 3: Default Approach
function possibleBipartition(n: number, dislikes: number[][]): boolean {
const color = new Array(n + 1).fill(0);
const g = Array.from({ length: n + 1 }, () => []);
const dfs = (i: number, v: number) => {
color[i] = v;
for (const j of g[i]) {
if (color[j] === color[i] || (color[j] === 0 && dfs(j, 3 ^ v))) {
return true;
}
}
return false;
};
for (const [a, b] of dislikes) {
g[a].push(b);
g[b].push(a);
}
for (let i = 1; i <= n; i++) {
if (color[i] === 0 && dfs(i, 1)) {
return false;
}
}
return true;
}func possibleBipartition(n int, dislikes [][]int) bool {
g := make([][]int, n)
for _, e := range dislikes {
a, b := e[0]-1, e[1]-1
g[a] = append(g[a], b)
g[b] = append(g[b], a)
}
color := make([]int, n)
var dfs func(int, int) bool
dfs = func(i, c int) bool {
color[i] = c
for _, j := range g[i] {
if color[j] == c {
return false
}
if color[j] == 0 && !dfs(j, 3-c) {
return false
}
}
return true
}
for i, c := range color {
if c == 0 && !dfs(i, 1) {
return false
}
}
return true
}impl Solution {
fn dfs(i: usize, v: usize, color: &mut Vec<usize>, g: &Vec<Vec<usize>>) -> bool {
color[i] = v;
for &j in (*g[i]).iter() {
if color[j] == color[i] || (color[j] == 0 && Self::dfs(j, v ^ 3, color, g)) {
return true;
}
}
false
}
pub fn possible_bipartition(n: i32, dislikes: Vec<Vec<i32>>) -> bool {
let n = n as usize;
let mut color = vec![0; n + 1];
let mut g = vec![Vec::new(); n + 1];
for d in dislikes.iter() {
let (i, j) = (d[0] as usize, d[1] as usize);
g[i].push(j);
g[j].push(i);
}
for i in 1..=n {
if color[i] == 0 && Self::dfs(i, 1, &mut color, &g) {
return false;
}
}
true
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Graph Coloring Using BFS | Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. |
| Approach 2: Graph Coloring Using DFS | Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph Coloring with BFS | O(n + m) | O(n + m) | Preferred iterative solution; easy to reason about level-by-level coloring |
| Graph Coloring with DFS | O(n + m) | O(n + m) | Good when recursion is comfortable; results in shorter code for bipartite checks |
Frequently asked questions
Is Possible Bipartition easy or hard?
Possible Bipartition is considered a Medium difficulty problem. The main challenge is recognizing that the dislike relationships form a graph and that the problem reduces to checking whether the graph is bipartite using BFS or DFS coloring.
Possible Bipartition Python/Java solution
Both Python and Java implementations follow the same idea: build the adjacency list, maintain a color array, and run BFS or DFS for each unvisited node. During traversal, assign opposite colors to neighbors and detect conflicts. The algorithm remains O(n + m) regardless of language.
How to solve Possible Bipartition in O(n)?
Build an adjacency list from the dislike pairs and run BFS or DFS to color the graph. Assign one color to the starting node and alternate colors for neighbors. If a neighbor already has the same color as the current node, return false. Since each node and edge is processed once, the runtime is O(n + m).
What is the best approach for Possible Bipartition?
The standard approach is to treat the dislikes list as a graph and check whether the graph is bipartite. You color nodes using two colors while traversing with BFS or DFS. If any edge connects two nodes with the same color, the bipartition is impossible. This solution runs in O(n + m) time where m is the number of dislike pairs.
Is Possible Bipartition asked at Google/Amazon/Meta?
Bipartite graph detection problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations include checking if a graph is bipartite, course scheduling constraints, and grouping problems with conflicts. This problem specifically tests graph traversal and coloring techniques.
What data structure is used in Possible Bipartition?
The solution uses an adjacency list to represent the graph and an array or map to store node colors. A queue is used for BFS implementations, while recursion or a stack is used for DFS traversal.
What is the time complexity of Possible Bipartition?
The optimal BFS or DFS graph traversal runs in O(n + m) time. Each person (node) is processed once and each dislike pair (edge) is examined at most twice in an undirected adjacency list. The space complexity is also O(n + m) due to the adjacency list and color array.