MediumDepth-First SearchBreadth-First SearchUnion FindGraphUpdated Sep 2026

886. Possible Bipartition

Asked at TikTok, Snowflake

Difficulty

Medium

Time

O(n + e)

Space

O(n + e)

Pattern

Depth-First Search

Companies

2

Problem

You have n people, numbered 1 to n. Some pairs of people dislike each other. You must put every person into one of two groups so that no two people who dislike each other land in the same group. Groups may have any size, including zero.

You are given the number n and a list dislikes, where each entry [a, b] means person a and person b dislike each other. Return true if such a split exists, otherwise return false.

Think of people as nodes and each dislike pair as an edge between them. The question becomes: can we paint every node with one of two colors so that the two ends of every edge get different colors? This is the classic bipartite graph check. A graph like this works if and only if it has no cycle of odd length.

Two groups, no dislike inside a group

groupsAB1423Example 1 works: 1 and 4 together, 2 and 3 togethergroupsAB1?23Example 2 fails: 2 and 3 dislike each other but mustshare group B
Each dislike pair must cross between the two groups; the triangle on the right makes that impossible.

Constraints

  • ●1 <= n <= 2000
  • ●0 <= dislikes.length <= 10^4
  • ●dislikes[i].length == 2
  • ●1 <= ai < bi <= n
  • ●All pairs in dislikes are unique

Examples

Example 1
Inputn = 4, dislikes = [[1,2],[1,3],[2,4]]
Outputtrue
WhyPut 1 and 4 in the first group, and 2 and 3 in the second. Every dislike pair crosses between the groups, so no pair shares a group.
Example 2
Inputn = 3, dislikes = [[1,2],[1,3],[2,3]]
Outputfalse
WhyThese three people form a triangle. If 1 is in group A, then 2 and 3 must both be in group B, but 2 and 3 dislike each other. So two groups are not enough.

Asked At

2 companies
CompanyDifficulty
TikTokMediumView all TikTok questions →
SnowflakeMediumView all Snowflake questions →

How to Think About It

1

Model people as nodes and each dislike pair as an undirected edge. Splitting into two groups with no internal edges is exactly a 2-coloring of the graph.

2

Key insight: BFS (or DFS) from any uncolored node, give it color 0, and give every neighbor the opposite color. If you ever find an edge whose endpoints have the same color, it is impossible.

3

The graph may be disconnected, so start a new BFS from every node that is still uncolored.

4

Equivalent characterization: a graph is bipartite iff it has no odd-length cycle. The coloring check detects such a cycle automatically.

5

Walkthrough: n = 3, dislikes [[1,2],[1,3],[2,3]] — a triangle. Color 1 red, 2 and 3 blue, but 2 and 3 dislike each other -> false.

Optimal Approach

Step 1: Build an adjacency list from dislikes.
Step 2: color = [-1] * (n + 1).
Step 3: For each person s with color[s] == -1:
Set color[s] = 0 and BFS.
For each neighbor v of u: if uncolored, set color[v] = 1 - color[u] and enqueue; if color[v] == color[u], return false.
Step 4: Return true.

Time: O(n + e). Space: O(n + e).

Two-coloring by BFS

color-0---01234startStart at person 1, color it 0color-011-01234Neighbors 2 and 3 of person 1 get the opposite color 1color-011001234Person 4 is a neighbor of 2, so it gets color 0 — noconflict, answer trueneighbor color = 1 − current colorsame color on an edge → return false
Give a start node color 0, give every neighbor the opposite color, and stop if an edge joins two nodes of the same color.
ComplexityTime O(n + e)Space O(n + e)Building the adjacency list and running BFS over every node and edge costs O(n + e), where e is the number of dislike pairs.

What Trips People Up in Real Interviews

1

Only starting BFS from person 1. Disconnected components must each be checked.

2

Using a directed graph. Dislike is symmetric — add both directions.

3

Off-by-one: people are numbered from 1 to n, so size arrays n + 1.

4

Trying greedy assignment in input order without propagation; it can place someone before their constraints are known.

Solution Code

O(n + e) time
from collections import deque

def possibleBipartition(n, dislikes):
    g = [[] for _ in range(n + 1)]
    for a, b in dislikes:
        g[a].append(b)
        g[b].append(a)
    color = [-1] * (n + 1)
    for s in range(1, n + 1):
        if color[s] != -1:
            continue
        color[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in g[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    q.append(v)
                elif color[v] == color[u]:
                    return False
    return True

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Possible Bipartition problem?

Possible Bipartition asks whether `n` people can be split into two groups so that no two people who dislike each other end up in the same group. Treat dislikes as edges and the question becomes: is this graph bipartite?

How do you solve Possible Bipartition?

The optimal approach runs in O(n + e) time and O(n + e) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Possible Bipartition?

Possible Bipartition is asked at TikTok, Snowflake. It is a medium difficulty problem.

What are common mistakes on Possible Bipartition?
  • Only starting BFS from person 1. Disconnected components must each be checked.
  • Using a directed graph. Dislike is symmetric — add both directions.
  • Off-by-one: people are numbered from 1 to `n`, so size arrays `n + 1`.
  • Trying greedy assignment in input order without propagation; it can place someone before their constraints are known.