Possible Bipartition - Solution & Explanation
Problem Statement
We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group.
Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.
Example 1:
Input: n = 4, dislikes = [[1,2],[1,3],[2,4]] Output: true Explanation: 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 Explanation: We need at least 3 groups to divide them. We cannot put them in two groups.
Constraints:
1 <= n <= 20000 <= dislikes.length <= 104dislikes[i].length == 21 <= ai < bi <= n- All the pairs of
dislikesare unique.
Approach Overview
Problem Overview: You are given n people and a list of dislike pairs. Each pair means those two people cannot be in the same group. The task is to check whether you can split everyone into two groups so that no pair of people who dislike each other end up in the same group.
The structure formed by dislikes is a graph where each person is a node and every dislike pair is an undirected edge. The problem reduces to checking whether this graph is bipartite. A graph is bipartite if its nodes can be colored using two colors such that no adjacent nodes share the same color.
Approach 1: Graph Coloring Using BFS (O(n + m) time, O(n + m) space)
Build an adjacency list from the dislikes array so you can quickly access all neighbors of a person. Maintain a color array where each node is assigned either 1 or -1. Iterate through all nodes because the graph may have multiple disconnected components. For every uncolored node, start a Breadth-First Search. Assign the starting node a color, then push it into a queue. While processing the queue, give each neighbor the opposite color. If you encounter a neighbor that already has the same color as the current node, the graph cannot be bipartite, so the partition is impossible. BFS works well here because it explores level by level and naturally alternates colors across edges.
Approach 2: Graph Coloring Using DFS (O(n + m) time, O(n + m) space)
The same bipartite check can be implemented using Depth-First Search. After constructing the adjacency list, recursively traverse the graph and assign alternating colors to neighbors. Each DFS call colors the current node and then explores all adjacent nodes. If a neighbor already has a conflicting color, you immediately return false. DFS tends to produce shorter code because the recursion naturally handles traversal, while BFS uses an explicit queue. Both methods rely on the same underlying graph traversal idea and produce identical time complexity.
In both solutions, the key insight is that dislike relationships form edges in a graph, and the two groups correspond to the two colors of a bipartite graph. The algorithm simply attempts to color the graph while respecting those constraints.
Recommended for interviews: The BFS graph-coloring solution is commonly expected because it clearly demonstrates understanding of bipartite graphs and iterative traversal. DFS is equally correct and sometimes shorter to implement. Interviewers mainly look for the insight that this is a bipartite graph problem and that coloring during traversal detects conflicts in O(n + m) time.
Approach 1: Approach 1: Graph Coloring Using BFS
This approach uses a BFS traversal to determine if the graph is bipartite. A graph is bipartite if you can color it using two colors such that no two adjacent nodes have the same color. We'll represent people as nodes and dislikes as edges.
The C solution uses a BFS approach to check if the graph can be bipartite. The graph is represented using an adjacency list, and BFS is performed from each uncolored node. If we find a conflict in colors, we return false.
Complexity
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges.
Space Complexity: O(V + E) for storing the graph structure.
Approach 2: Approach 2: Graph Coloring Using DFS
This approach uses a DFS traversal to determine if the graph is bipartite. Similar to BFS, DFS attempts to color the graph using two colors to check if a valid bipartition is possible.
The C solution uses a recursive DFS approach to attempt coloring with two colors. If two adjacent nodes have the same color during the traversal, the graph is not bipartite.
Complexity
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges.
Space Complexity: O(V + E) for graph representation.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Graph Coloring Using BFS | Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. |
| Approach 2: Graph Coloring Using DFS | Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph Coloring with BFS | O(n + m) | O(n + m) | Preferred iterative solution; easy to reason about level-by-level coloring |
| Graph Coloring with DFS | O(n + m) | O(n + m) | Good when recursion is comfortable; results in shorter code for bipartite checks |
Video Solution
Possible Bipartition | Bipartite graph | Graph coloring | Leetcode #886 • Techdose • 55,536 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Possible Bipartition easy or hard?
Possible Bipartition Python/Java solution
How to solve Possible Bipartition in O(n)?
What is the best approach for Possible Bipartition?
Is Possible Bipartition asked at Google/Amazon/Meta?
What data structure is used in Possible Bipartition?
What is the time complexity of Possible Bipartition?
Ready to solve this problem?
Practice Possible Bipartition with our built-in code editor and test cases.
Practice on FleetCode