Is Possible Bipartition easy or hard?

Possible Bipartition is considered a Medium difficulty problem. The main challenge is recognizing that the dislike relationships form a graph and that the problem reduces to checking whether the graph is bipartite using BFS or DFS coloring.

Possible Bipartition Python/Java solution

Both Python and Java implementations follow the same idea: build the adjacency list, maintain a color array, and run BFS or DFS for each unvisited node. During traversal, assign opposite colors to neighbors and detect conflicts. The algorithm remains O(n + m) regardless of language.

How to solve Possible Bipartition in O(n)?

Build an adjacency list from the dislike pairs and run BFS or DFS to color the graph. Assign one color to the starting node and alternate colors for neighbors. If a neighbor already has the same color as the current node, return false. Since each node and edge is processed once, the runtime is O(n + m).

What is the best approach for Possible Bipartition?

The standard approach is to treat the dislikes list as a graph and check whether the graph is bipartite. You color nodes using two colors while traversing with BFS or DFS. If any edge connects two nodes with the same color, the bipartition is impossible. This solution runs in O(n + m) time where m is the number of dislike pairs.

Is Possible Bipartition asked at Google/Amazon/Meta?

Bipartite graph detection problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations include checking if a graph is bipartite, course scheduling constraints, and grouping problems with conflicts. This problem specifically tests graph traversal and coloring techniques.

What data structure is used in Possible Bipartition?

The solution uses an adjacency list to represent the graph and an array or map to store node colors. A queue is used for BFS implementations, while recursion or a stack is used for DFS traversal.

What is the time complexity of Possible Bipartition?

The optimal BFS or DFS graph traversal runs in O(n + m) time. Each person (node) is processed once and each dislike pair (edge) is examined at most twice in an undirected adjacency list. The space complexity is also O(n + m) due to the adjacency list and color array.

Description Solution Video 23:34

886. Possible Bipartition

Medium53.0% acceptance11 companies

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] = [a_i, b_i] indicates that the person labeled a_i does not like the person labeled b_i, 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 <= 2000
0 <= dislikes.length <= 10⁴
dislikes[i].length == 2
1 <= a_i < b_i <= n
All the pairs of dislikes are unique.

Asked at 11 companies

Samsung Tiktok Snowflake Meesho LinkedIn Microsoft Snapchat Uber

Google Amazon Meta

Topics

23:34

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

4
[[1,2],[1,3],[2,4]]

Input

3
[[1,2],[1,3],[2,3]]

Your code is saved on this device.Solution