Possible Bipartition

Possible Bipartition

What is this problem about?

The Possible Bipartition problem gives you a list of dislikes between people (they can't be in the same group) and asks whether it's possible to divide everyone into two groups with no dislikes within a group. This is equivalent to checking if the dislikes graph is bipartite. The union find, BFS, graph, and DFS interview pattern is the core.

Why is this asked in interviews?

Samsung, Uber, Microsoft, Meta, Amazon, TikTok, Google, and Bloomberg ask this because bipartite graph checking is a fundamental graph algorithm used in assignment problems, scheduling, and social network analysis. Both BFS/DFS coloring and Union-Find approaches are valid.

Algorithmic pattern used

BFS/DFS graph coloring. Build the dislikes graph as an adjacency list. BFS/DFS: assign color 0 to the first node of each component. For each neighbor: if not colored, assign opposite color; if colored same as current, return false (odd cycle detected). If all nodes are 2-colorable, return true.

Example explanation

n=4, dislikes=[[1,2],[1,3],[2,4]].

• Color 1 with 0. Color 2 with 1 (dislike 1). Color 3 with 1 (dislike 1). Color 4 with 0 (dislike 2). No conflicts. Return true (group A={1,4}, group B={2,3}).

n=3, dislikes=[[1,2],[1,3],[2,3]]: triangle (odd cycle). Color 1=0,2=1,3=1. Check 2-3: both color 1 → conflict. Return false.

Common mistakes candidates make

• Not handling disconnected components (must start BFS/DFS from every unvisited node).
• Directed vs undirected: dislikes are undirected (must add both directions to adjacency list).
• Union-Find approach: must union each pair's "enemy" and check for self-loop.
• Not detecting odd-length cycles correctly.

Interview preparation tip

Possible Bipartition and "Is Graph Bipartite?" are the same problem. Bipartite checking = 2-colorable = no odd cycles. BFS coloring is clean: color alternately, detect same-color neighbors. The Union-Find approach: for each pair (a, b) with a disliking b, union a with all of b's dislikes and vice versa. Practice both approaches until fluent — they're asked separately at different companies.