This problem requires splitting n people into two groups where no one in a group dislikes another. Using depth-first search or breadth-first search, you can attempt to color the graph with two colors and detect conflicts. Union-Find also works to track connected components and ensure no two conflicting nodes are in the same set, returning true if a valid bipartition exists.
Problem Statement
You are given n people labeled from 1 to n. Each person may dislike certain others, and the goal is to divide everyone into two groups so that no person is in the same group as someone they dislike.
Given an integer n and an array dislikes where dislikes[i] = [ai, bi] indicates that person ai dislikes person bi, return true if it is possible to split all people into two groups without placing conflicting individuals together. For example, n = 4, dislikes = [[1,2],[1,3],[2,4]] returns true because a valid split exists.
Examples
Example 1
Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
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
We need at least 3 groups to divide them. We cannot put them in two groups.
Constraints
- 1 <= n <= 2000
- 0 <= dislikes.length <= 104
- dislikes[i].length == 2
- 1 <= ai < bi <= n
- All the pairs of dislikes are unique.
Solution Approach
Graph Coloring with DFS
Construct a graph where nodes represent people and edges represent dislikes. Use depth-first search to try coloring each node with one of two colors while ensuring adjacent nodes receive opposite colors. If a conflict occurs, return false; otherwise, return true.
Breadth-First Search Variation
Use BFS to traverse the graph iteratively. Start from each unvisited node, assign a color, and enqueue neighbors with the opposite color. Detect conflicts if a neighbor already has the same color. BFS provides similar guarantees as DFS and can handle large graphs efficiently.
Union-Find Method
Treat each dislike pair as a connection that enforces group separation. Use Union-Find to maintain sets of people and merge non-conflicting connections. If any two people who dislike each other end up in the same set, return false. This approach is effective for batch conflict detection and simplifies repeated checks.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(N + E) where N is the number of people and E is the number of dislikes for DFS/BFS, and almost O(E*α(N)) for Union-Find; space is O(N + E) for adjacency lists or O(N) for Union-Find arrays.
What Interviewers Usually Probe
- Are you able to model dislikes as a graph and identify conflicts quickly?
- Can you implement two-color graph coloring efficiently?
- Do you understand both DFS and BFS trade-offs in this context?
Common Pitfalls or Variants
Common pitfalls
- Forgetting to check all disconnected components, which may miss a conflict.
- Assigning colors incorrectly leading to false positive bipartitions.
- Assuming Union-Find alone without proper separation logic guarantees correctness.
Follow-up variants
- Allowing more than two groups and checking k-partition feasibility.
- Input graph may contain cycles or disconnected subgraphs, testing traversal robustness.
- Edge list may be large and require optimized adjacency representation to avoid TLE.
How GhostInterview Helps
- GhostInterview provides step-by-step DFS/BFS traversal guides specific to bipartition conflicts.
- It highlights common mistakes like color misassignment and disconnected component handling.
- Offers pattern-specific hints on using Union-Find to detect impossible bipartitions efficiently.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main pattern used in Possible Bipartition?
The main pattern is graph traversal with depth-first search or breadth-first search to perform two-color graph coloring.
Can Union-Find solve Possible Bipartition?
Yes, Union-Find can track groups and detect conflicts, ensuring no two people who dislike each other are in the same set.
What should I watch out for when implementing DFS here?
Be careful to visit all disconnected components and maintain correct coloring to avoid false positives.
How does BFS compare to DFS for this problem?
BFS iteratively colors nodes and detects conflicts similarly to DFS but can be easier to manage for large graphs with iterative queues.
What is a common reason Possible Bipartition returns false?
A conflict occurs when two people who dislike each other are forced into the same group, making a two-group split impossible.
Need direct help with Possible Bipartition instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Possible Bipartition from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Identify which single infected node to remove to minimize total malware spread in a connected network graph efficiently.
Open problem page#928 Minimize Malware Spread IIMinimize Malware Spread II asks to minimize the spread of malware in a network of nodes by removing one infected node.
Open problem page#785 Is Graph Bipartite?Determine whether an undirected graph can be split into two independent sets using DFS, BFS, or Union Find patterns.
Open problem page