2Brute2Best
🔥0

Possible Bipartition

Medium·LeetCode #886 Pro OnlyBasic Reinforcement
LeetCode
01

Problem Statement

There are n people, numbered from 1 to n. Some pairs of people do not like each other. The list dislikes gives those pairs, where [a, b] means person a does not like person b.

You want to split everyone into two groups. Two people who dislike each other must not be in the same group. Groups may have any size.

Return true if such a split exists, otherwise false.

Input

n, the number of people, and dislikes, a list of pairs [a, b].

Output

true if the people can be split into two groups with no dislike inside one group, otherwise false.

Example 1
Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true

Put persons 1 and 4 in one group, and persons 2 and 3 in the other. Every dislike joins the two groups.

Example 2
Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

All three people dislike each other. With only two groups, two of them must share a group.

Constraints
  • • 1 ≤ n ≤ 2000
  • • 0 ≤ dislikes.length ≤ 10^4
  • • dislikes[i].length = 2
  • • 1 ≤ a_i < b_i ≤ n
  • • All the pairs in dislikes are unique.
02

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“do not like each other”
→ A dislike is an edge. The two people become two nodes, and the edge means they must get different colours.
“split everyone into two groups”
→ Two groups are two colours: a 2-colouring of the graph.
“n people numbered from 1”
→ Build the graph with n + 1 slots so person n has a slot, and count from 1.
03

Approach Complexity Ladder

Brute Force — try every split of the peopleO(2^N · E)O(1)

Try all 2^n splits; accept the first one where no dislike pair shares a group

Optimal — build the graph, then BFS two-colouringO(N + E)O(N + E)

One edge per dislike, added both ways; BFS two-colouring; a clash means false

Brute Force Intuition

Give every person group A or B, for all 2^n splits. A split works when no dislike pair has both people in the same group. Each person has two choices, so the brute force tries 2^n splits, and that is only practical for small n.

Recognition rule for this sub-pattern:

Colour a node, give neighbours the opposite colour; a clash means not bipartite.
Remember this · Graph BFS / DFS
Trigger
Grid of cells, islands, regions, "minimum steps", transformations between states, connected components.
Think
What is a node, what is an edge, and do I need the shortest path or just reachability?
Key question
How do I mark visited so I never process a node twice?
Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms
Interactive step-by-step playback with pointer & array state transitions
52 comprehensive LLD chapters
Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions
40 C++ basics labs & hardware memory models
Vtables, byte layouts, assembly insights, and multi-threading race conditions
Production-ready C++23 source code
Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways
Create Free AccountLog in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Food Delivery System (Zomato / DoorDash)

Geospatial indexing and shortest dispatch routing for delivery partners.

Explore Track
C++ Internals

Virtual Method Table (vtable) & Dynamic Dispatch

Polymorphic graph nodes and state machine execution overhead.

Explore Track
Is Graph Bipartite?