Possible Bipartition — Solution in Python, Java & C++
Possible Bipartition solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Possible Bipartition is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Graph, Union Find
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A group of n people labelled 1 through n must be split into two groups of any size. dislikes[i] = [a, b] means a and b refuse to be in the same group.
Return true if such a split is possible.
Example 1
Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: Groups {1,4} and {2,3}.
Example 2
Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
Example 3
Input: n = 1, dislikes = []
Output: true
Constraints
1 <= n <= 300 <= dislikes.length <= 601 <= dislikes[i][0] < dislikes[i][1] <= nThere are no duplicate pairs.
Hints for Possible Bipartition
Hint 1
Build a graph where an edge means "must be apart" — the question is whether it is bipartite.
Hint 2
Two-colour it with BFS or DFS, giving each neighbour the opposite colour.
Hint 3
Start from every uncoloured person, since the dislike graph may be disconnected.
How to solve Possible Bipartition
Build the dislike graph and test whether it is bipartite by two-colouring with BFS.
Approach
- Adjacency list from
dislikes. - For each uncoloured person, BFS assigning opposite colours; fail on a same-colour neighbour.
Why it works
The two groups are the two colour classes; a valid split exists iff the graph has no odd cycle.
Complexity
- Time —
O(n + d) - Space —
O(n + d)
Pitfalls
- People are 1-indexed; size the arrays
n + 1.
Reference solution
Python
from collections import deque
def possibleBipartition(n: int, dislikes) -> bool:
adjacency = [[] for _ in range(n + 1)]
for a, b in dislikes:
adjacency[a].append(b)
adjacency[b].append(a)
color = [0] * (n + 1)
for start in range(1, n + 1):
if color[start] != 0:
continue
color[start] = 1
queue = deque([start])
while queue:
node = queue.popleft()
for nxt in adjacency[node]:
if color[nxt] == 0:
color[nxt] = -color[node]
queue.append(nxt)
elif color[nxt] == color[node]:
return False
return TrueJava
public static boolean possibleBipartition(int n, int[][] dislikes) {
List<List<Integer>> adjacency = new ArrayList<>();
for (int i = 0; i <= n; i++) adjacency.add(new ArrayList<>());
for (int[] pair : dislikes) {
adjacency.get(pair[0]).add(pair[1]);
adjacency.get(pair[1]).add(pair[0]);
}
int[] color = new int[n + 1];
for (int start = 1; start <= n; start++) {
if (color[start] != 0) continue;
color[start] = 1;
Deque<Integer> queue = new ArrayDeque<>();
queue.addLast(start);
while (!queue.isEmpty()) {
int node = queue.pollFirst();
for (int next : adjacency.get(node)) {
if (color[next] == 0) {
color[next] = -color[node];
queue.addLast(next);
} else if (color[next] == color[node]) {
return false;
}
}
}
}
return true;
}C++
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
vector<vector<int>> adjacency(n + 1);
for (const auto& pair : dislikes) {
adjacency[pair[0]].push_back(pair[1]);
adjacency[pair[1]].push_back(pair[0]);
}
vector<int> color(n + 1, 0);
for (int start = 1; start <= n; start++) {
if (color[start] != 0) continue;
color[start] = 1;
vector<int> queue;
queue.push_back(start);
size_t head = 0;
while (head < queue.size()) {
int node = queue[head++];
for (int next : adjacency[node]) {
if (color[next] == 0) {
color[next] = -color[node];
queue.push_back(next);
} else if (color[next] == color[node]) {
return false;
}
}
}
}
return true;
}JavaScript
var possibleBipartition = function(n, dislikes) {
const adjacency = [];
for (let i = 0; i <= n; i++) adjacency.push([]);
for (let i = 0; i < dislikes.length; i++) {
adjacency[dislikes[i][0]].push(dislikes[i][1]);
adjacency[dislikes[i][1]].push(dislikes[i][0]);
}
const color = [];
for (let i = 0; i <= n; i++) color.push(0);
for (let start = 1; start <= n; start++) {
if (color[start] !== 0) continue;
color[start] = 1;
const queue = [start];
let head = 0;
while (head < queue.length) {
const node = queue[head++];
for (let i = 0; i < adjacency[node].length; i++) {
const next = adjacency[node][i];
if (color[next] === 0) {
color[next] = -color[node];
queue.push(next);
} else if (color[next] === color[node]) {
return false;
}
}
}
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)