LeetCode 886 - Possible Bipartition

This problem asks whether it is possible to divide n people into exactly two groups such that no pair of people who dislike each other end up in the same group.

leetcodemediumdepth-first-searchbreadth-first-searchunion-findgraph-theory

LeetCode Problem 886

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory

Solution

Problem Understanding

This problem asks whether it is possible to divide n people into exactly two groups such that no pair of people who dislike each other end up in the same group.

The input contains:

  • An integer n, representing people labeled from 1 to n
  • A list dislikes, where each pair [a, b] means person a and person b cannot belong to the same group

The task is to return:

  • true if such a division into two groups is possible
  • false otherwise

This is fundamentally a graph problem. Each person can be viewed as a node, and each dislike relationship is an undirected edge between two nodes. The problem then becomes:

Can we color the graph using only two colors so that no adjacent nodes share the same color?

That is exactly the definition of a bipartite graph.

For example, if person 1 dislikes persons 2 and 3, then 1 must be placed in the opposite group from both 2 and 3.

The constraints are important:

  • n <= 2000
  • dislikes.length <= 10000

These limits are large enough that exponential or brute-force partitioning approaches are infeasible. We need a graph algorithm with roughly linear complexity relative to the number of nodes and edges.

Several edge cases are important:

  • A graph with no dislike relationships is always bipartite
  • The graph may contain multiple disconnected components
  • Odd cycles make bipartition impossible
  • Even cycles are valid
  • A single person with no edges should not cause issues
  • The graph is undirected, so every dislike relationship must be added in both directions

Approaches

Brute Force Approach

A brute-force solution would try every possible assignment of people into two groups.

Since each person has two choices, the total number of possible partitions is:

$$2^n$$

For each partition, we would check every dislike pair to ensure both people are not in the same group.

This approach is correct because it exhaustively explores all valid configurations. If any partition satisfies the conditions, we return true.

However, this becomes computationally impossible very quickly. With n = 2000, the number of partitions is astronomically large.

The brute-force method therefore cannot work within the constraints.

Optimal Approach, Graph Bipartite Checking

The key observation is that this problem is exactly the bipartite graph problem.

If we treat:

  • each person as a node
  • each dislike relationship as an undirected edge

then the problem asks whether the graph can be divided into two sets such that every edge connects nodes from different sets.

This can be solved using either:

  • Breadth-First Search
  • Depth-First Search

while assigning one of two colors to each node.

The idea is:

  • Assign a color to a starting node
  • Every neighbor must receive the opposite color
  • Continue traversing the graph
  • If we ever find two adjacent nodes with the same color, the graph is not bipartite

Because the graph may be disconnected, we must start a traversal from every unvisited node.

This approach is efficient because every node and edge is processed only a small number of times.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n × m) O(n) Tries every possible partition
Optimal O(n + m) O(n + m) Uses graph coloring with BFS or DFS

Here, m is the number of dislike relationships.

Algorithm Walkthrough

We will use Breadth-First Search with graph coloring.

Step 1: Build the Graph

Create an adjacency list where:

  • graph[a] contains all people disliked by a
  • Since dislikes are mutual constraints, add edges in both directions

For example:

dislikes = [[1,2],[1,3]]

becomes:

1 -> [2,3]
2 -> [1]
3 -> [1]

An adjacency list is efficient because it allows fast traversal of neighbors.

Step 2: Create a Color Array

We maintain an array called color:

  • 0 means unvisited
  • 1 means first group
  • -1 means second group

This lets us efficiently track group assignments.

Step 3: Traverse Every Component

The graph may not be fully connected.

For example:

1 -- 2

3 -- 4

If we only start BFS from node 1, nodes 3 and 4 would never be processed.

So we loop through every person from 1 to n.

Whenever we find an uncolored node, we start a new BFS.

Step 4: Start BFS

Assign the starting node a color:

color[start] = 1

Push it into a queue.

Step 5: Process Neighbors

While the queue is not empty:

  1. Remove the current node
  2. Visit all neighbors
  3. If a neighbor is uncolored:
  • assign opposite color
  • add it to queue
  1. If a neighbor already has the same color:
  • return False

The opposite color is obtained using:

-color[current]

Step 6: Finish Traversal

If BFS completes for every component without conflicts, the graph is bipartite.

Return True.

Why It Works

The algorithm maintains the invariant that every edge connects nodes with opposite colors.

Whenever we visit a node, all of its neighbors are forced into the opposite group. If we ever encounter an edge connecting two nodes with the same color, then no valid bipartition exists.

This correctly detects odd cycles, which are exactly the structures that make a graph non-bipartite.

Python Solution

from collections import deque
from typing import List

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        graph = [[] for _ in range(n + 1)]

        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)

        color = [0] * (n + 1)

        for person in range(1, n + 1):
            if color[person] != 0:
                continue

            queue = deque([person])
            color[person] = 1

            while queue:
                current = queue.popleft()

                for neighbor in graph[current]:
                    if color[neighbor] == 0:
                        color[neighbor] = -color[current]
                        queue.append(neighbor)
                    elif color[neighbor] == color[current]:
                        return False

        return True

The implementation begins by constructing an adjacency list. Since the graph is undirected, each dislike pair is inserted in both directions.

The color array stores group assignments. A value of 0 indicates the node has not yet been visited.

We iterate through all people because the graph may contain disconnected components. Whenever an uncolored node is found, we launch a BFS traversal from that node.

Inside BFS, each neighbor receives the opposite color of the current node. If a neighbor already has the same color as the current node, the graph cannot be bipartite, so we immediately return False.

If all nodes are processed successfully, the graph satisfies bipartite conditions and we return True.

Go Solution

func possibleBipartition(n int, dislikes [][]int) bool {
	graph := make([][]int, n+1)

	for _, edge := range dislikes {
		a, b := edge[0], edge[1]
		graph[a] = append(graph[a], b)
		graph[b] = append(graph[b], a)
	}

	color := make([]int, n+1)

	for person := 1; person <= n; person++ {
		if color[person] != 0 {
			continue
		}

		queue := []int{person}
		color[person] = 1

		for len(queue) > 0 {
			current := queue[0]
			queue = queue[1:]

			for _, neighbor := range graph[current] {
				if color[neighbor] == 0 {
					color[neighbor] = -color[current]
					queue = append(queue, neighbor)
				} else if color[neighbor] == color[current] {
					return false
				}
			}
		}
	}

	return true
}

The Go implementation follows the same logic as the Python version.

Slices are used for both the adjacency list and the BFS queue. Since Go does not provide a built-in deque structure, queue operations are implemented using slice slicing.

The color slice uses integers exactly like the Python version:

  • 0 for unvisited
  • 1 for one group
  • -1 for the other group

No integer overflow concerns exist because all operations involve only small integers.

Worked Examples

Example 1

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

Graph

1 -> [2,3]
2 -> [1,4]
3 -> [1]
4 -> [2]

BFS Traversal

Step Current Node Queue Color State
Start 1 [1] [0,1,0,0,0]
Process 1 1 [2,3] [0,1,-1,-1,0]
Process 2 2 [3,4] [0,1,-1,-1,1]
Process 3 3 [4] [0,1,-1,-1,1]
Process 4 4 [] [0,1,-1,-1,1]

No conflicts occur.

Return:

true

Valid groups:

Group A: [1,4]
Group B: [2,3]

Example 2

Input:
n = 3
dislikes = [[1,2],[1,3],[2,3]]

Graph

1 -> [2,3]
2 -> [1,3]
3 -> [1,2]

BFS Traversal

Step Current Node Queue Color State
Start 1 [1] [0,1,0,0]
Process 1 1 [2,3] [0,1,-1,-1]
Process 2 2 [3] conflict

When processing node 2, neighbor 3 already has the same color -1.

This means:

2 and 3 dislike each other
but are forced into the same group

Return:

false

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Every node and edge is processed at most once
Space O(n + m) Adjacency list, queue, and color array

Here:

  • n is the number of people
  • m is the number of dislike pairs

The adjacency list stores every edge twice because the graph is undirected. BFS visits each node once and examines each edge once.

Test Cases

from typing import List

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        from collections import deque

        graph = [[] for _ in range(n + 1)]

        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)

        color = [0] * (n + 1)

        for person in range(1, n + 1):
            if color[person] != 0:
                continue

            queue = deque([person])
            color[person] = 1

            while queue:
                current = queue.popleft()

                for neighbor in graph[current]:
                    if color[neighbor] == 0:
                        color[neighbor] = -color[current]
                        queue.append(neighbor)
                    elif color[neighbor] == color[current]:
                        return False

        return True

sol = Solution()

assert sol.possibleBipartition(4, [[1,2],[1,3],[2,4]]) is True
# basic bipartite graph

assert sol.possibleBipartition(3, [[1,2],[1,3],[2,3]]) is False
# odd cycle triangle

assert sol.possibleBipartition(5, []) is True
# no dislike edges

assert sol.possibleBipartition(1, []) is True
# single node graph

assert sol.possibleBipartition(2, [[1,2]]) is True
# simplest valid edge

assert sol.possibleBipartition(4, [[1,2],[2,3],[3,4],[4,1]]) is True
# even cycle

assert sol.possibleBipartition(5, [[1,2],[2,3],[3,4],[4,5],[5,1]]) is False
# odd cycle

assert sol.possibleBipartition(
    10,
    [[1,2],[3,4],[5,6],[7,8]]
) is True
# disconnected components

assert sol.possibleBipartition(
    6,
    [[1,2],[2,3],[3,1],[4,5]]
) is False
# one disconnected component is invalid

assert sol.possibleBipartition(
    8,
    [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,8]]
) is True
# long chain graph

Test Case Summary

Test Why
[[1,2],[1,3],[2,4]] Standard valid bipartite graph
[[1,2],[1,3],[2,3]] Triangle creates odd cycle
[] with multiple nodes No edges should always work
Single node Smallest valid input
Single edge Simplest nontrivial graph
Even cycle Even cycles are bipartite
Odd cycle Odd cycles are not bipartite
Disconnected graph Ensures all components are processed
Mixed valid and invalid components One invalid component should fail entire graph
Long chain Tests linear graph traversal

Edge Cases

Empty Dislike List

If dislikes is empty, no restrictions exist between people. Any partition is valid.

A naive implementation might incorrectly assume every node must be connected or visited through edges. Our solution correctly handles this because every unvisited node starts its own BFS traversal, even if it has no neighbors.

Disconnected Components

The graph may contain several isolated sections.

For example:

1 -- 2

3 -- 4

If the algorithm only starts BFS from node 1, it would completely miss nodes 3 and 4.

Our implementation prevents this by iterating through every person from 1 to n and launching BFS whenever an unvisited node is found.

Odd Cycles

Odd cycles are the critical structure that makes bipartition impossible.

For example:

1 -- 2
 \  /
  3

When traversing this graph, eventually two adjacent nodes are forced to share the same color.

The implementation explicitly checks:

elif color[neighbor] == color[current]:
    return False

This immediately detects invalid configurations.

Isolated Nodes

Some people may not appear in any dislike pair.

For example:

n = 5
dislikes = [[1,2]]

People 3, 4, and 5 are isolated.

The algorithm correctly handles them because isolated nodes simply start and finish BFS immediately without conflicts.