Possible Bipartition
Reported by candidates from Maven Clinic's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Three people who all dislike each other can't be split into two groups, and that tiny triangle is the whole idea behind the Maven Clinic OA question reported in August 2024. It's Possible Bipartition: n people, a list of dislike pairs, return true if two groups can satisfy every pair. It's a graph coloring problem in disguise. If you've seen bipartite checks, this is a ten minute job. If you haven't, the wording hides it well. StealthCoder sits invisibly on your screen as a safety net if you blank during the live OA, but the pattern below is short enough to carry in your head.
The problem
There are n people labeled from 1 to n. Each pair [a, b] in dislikes means that a and b must be placed in different groups.
Return true if all people can be split into two groups satisfying every pair, otherwise return false.
Function
possibleBipartition(n: int, dislikes: int[][]) → boolean
Examples
Example 1
n = 4
dislikes = [[1,2],[1,3],[2,4]]
return = true
One valid split is {1,4} and {2,3}.
Example 2
n = 3
dislikes = [[1,2],[1,3],[2,3]]
return = false
The three people form an odd cycle, so two groups are impossible.
Constraints
1 <= n <= 2000.
0 <= dislikes.length <= 10000.
1 <= a, b <= n and a != b.
No dislike pair is duplicated.Reported by candidates. Source: FastPrep
Pattern and pitfall
Treat each person as a node and each dislike as an edge. The question becomes: is the graph bipartite? Build an adjacency list, then color nodes with two colors using BFS or DFS. Start from every uncolored node, because the graph can be disconnected and people with no dislikes still count. Give a neighbor the opposite color. If a neighbor already has your color, return false. Union-find with a dislike-partner trick also works, but coloring is easier to get right under pressure. The common pitfalls are skipping disconnected components, using 0-indexed arrays for 1-indexed people, and recursing deep with n up to 2000, so prefer iterative BFS if your language has a low recursion limit. Complexity is O(n + edges). If your mind goes blank mid-assessment, StealthCoder can surface this coloring solution in real time, but you shouldn't need it once the odd cycle idea clicks.
If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.
You can drill Possible Bipartition cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken.
Get StealthCoderRelated leaked OAs
This OA pattern shows up on LeetCode as possible bipartition. If you have time before the OA, drill that.
You've seen the question.
Make sure you actually pass Maven Clinic's OA.
Maven Clinic reuses patterns across OAs. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Possible Bipartition FAQ
What's the trick to Possible Bipartition?+
Model it as a graph and check if it's bipartite. Each dislike is an edge, and you two-color the nodes so every edge connects different colors. Any odd cycle makes it impossible, which is exactly what Example 2 shows with three mutual dislikes.
BFS, DFS, or union-find?+
Any works. BFS with a color array is the safest, since it avoids recursion depth issues at n = 2000 and is easy to debug. DFS is shorter to write. Union-find works too but takes more explaining. Pick the one you can write without thinking.
What edge cases break most solutions?+
Disconnected graphs are the big one. You must launch a coloring from every uncolored person, not just person 1. Also watch for empty dislikes, which should return true, and 1-indexed labels causing off-by-one errors in your arrays.
How hard is this really?+
Medium. The code is short, around 20 lines. The difficulty is recognizing it as bipartite checking. Once you see that, it's standard graph coloring. Candidates who miss it usually try greedy grouping and get stuck on conflicts.
How do I prepare in 48 hours for this Maven Clinic OA?+
Write the BFS coloring solution from scratch twice, then test it on both examples and a disconnected case. Review adjacent graph basics like building adjacency lists and cycle detection. Don't spend time on exotic algorithms. This one is about a single clean pattern.