Possible Bipartition
Asked at TikTok, Snowflake
Problem
Possible Bipartition asks whether n people can be split into two groups so that no two people who dislike each other end up in the same group. Treat dislikes as edges and the question becomes: is this graph bipartite?
Asked At
| Company | Difficulty | |
|---|---|---|
| TikTok | Medium | View all TikTok questions → |
| Snowflake | Medium | View all Snowflake questions → |
How to Think About It
Model people as nodes and each dislike pair as an undirected edge. Splitting into two groups with no internal edges is exactly a 2-coloring of the graph.
Key insight: BFS (or DFS) from any uncolored node, give it color 0, and give every neighbor the opposite color. If you ever find an edge whose endpoints have the same color, it is impossible.
The graph may be disconnected, so start a new BFS from every node that is still uncolored.
Equivalent characterization: a graph is bipartite iff it has no odd-length cycle. The coloring check detects such a cycle automatically.
Walkthrough: n = 3, dislikes [[1,2],[1,3],[2,3]] — a triangle. Color 1 red, 2 and 3 blue, but 2 and 3 dislike each other -> false.
Optimal Approach
Step 1: Build an adjacency list from dislikes.
Step 2: color = [-1] * (n + 1).
Step 3: For each person s with color[s] == -1:
Set color[s] = 0 and BFS.
For each neighbor v of u: if uncolored, set color[v] = 1 - color[u] and enqueue; if color[v] == color[u], return false.
Step 4: Return true.
Time: O(n + e). Space: O(n + e).
What Trips People Up in Real Interviews
Only starting BFS from person 1. Disconnected components must each be checked.
Using a directed graph. Dislike is symmetric — add both directions.
Off-by-one: people are numbered from 1 to n, so size arrays n + 1.
Trying greedy assignment in input order without propagation; it can place someone before their constraints are known.
Solution Code
from collections import deque
def possibleBipartition(n, dislikes):
g = [[] for _ in range(n + 1)]
for a, b in dislikes:
g[a].append(b)
g[b].append(a)
color = [-1] * (n + 1)
for s in range(1, n + 1):
if color[s] != -1:
continue
color[s] = 0
q = deque([s])
while q:
u = q.popleft()
for v in g[u]:
if color[v] == -1:
color[v] = 1 - color[u]
q.append(v)
elif color[v] == color[u]:
return False
return TrueFrequently Asked Questions
What is the Possible Bipartition problem?
Possible Bipartition asks whether `n` people can be split into two groups so that no two people who dislike each other end up in the same group. Treat dislikes as edges and the question becomes: is this graph bipartite?
How do you solve Possible Bipartition?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Possible Bipartition?
Possible Bipartition is asked at TikTok, Snowflake. It is a medium difficulty problem.
What are common mistakes on Possible Bipartition?
- Only starting BFS from person 1. Disconnected components must each be checked.
- Using a directed graph. Dislike is symmetric — add both directions.
- Off-by-one: people are numbered from 1 to `n`, so size arrays `n + 1`.
- Trying greedy assignment in input order without propagation; it can place someone before their constraints are known.