LeetCode 886: Possible Bipartition

Problem Restatement

We are given n people labeled from 1 to n.

We are also given a list dislikes, where each pair:

[a, b]

means person a dislikes person b, and person b dislikes person a.

We need to split everyone into two groups so that no pair of people who dislike each other are in the same group.

Return true if this is possible. Otherwise, return false.

This is exactly a bipartite graph problem: people are nodes, dislikes are edges, and we need to color the graph with two colors so that every edge connects nodes of different colors. The official constraints allow n <= 2000 and up to 10^4 dislike pairs.

Input and Output

Function shape:

def possibleBipartition(self, n: int, dislikes: list[list[int]]) -> bool:
    ...

Examples

Example 1:

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

One valid split is:

Check every dislike pair:

So the answer is true.

Example 2:

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

This forms a triangle:

1 dislikes 2
1 dislikes 3
2 dislikes 3

With only two groups, two of these people must share a group. But every pair dislikes each other, so this is impossible.

First Thought: Try Assigning Groups Recursively

A direct idea is to try all possible assignments of people to two groups.

Each person can go into group A or group B.

For n people, that gives:

2^n

possible assignments.

For each assignment, we could check whether any dislike pair is inside the same group.

This is correct, but much too slow for n <= 2000.

We need to use the structure of the dislike relationships.

Key Insight

Think of the problem as a graph.

We need to color every node using two colors.

For every edge [a, b], nodes a and b must have different colors.

So the question becomes:

Is the graph bipartite?

A graph is bipartite if its nodes can be divided into two sets so that every edge goes between the two sets.

We can test this using DFS or BFS.

Algorithm

Build an adjacency list.

For each dislike pair [a, b]:

graph[a].append(b)
graph[b].append(a)

Use an array color.

Then scan all people from 1 to n.

If a person is uncolored, start a DFS or BFS from that person and assign color 1.

For each edge from person to neighbor:

1. If neighbor is uncolored, color it with the opposite color.
2. If neighbor already has the same color as person, return false.

If all connected components are colored successfully, return true.

We must scan all people because the graph may be disconnected.

Walkthrough

Use:

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

Build the graph:

Start at person 1.

Assign:

color[1] = 1

Neighbors 2 and 3 must get the opposite color:

color[2] = -1
color[3] = -1

From person 2, neighbor 4 must get the opposite color:

color[4] = 1

Final colors:

Every dislike edge connects different colors, so the split is possible.

Correctness

The algorithm assigns colors so that every dislike edge connects two people in different groups.

When the algorithm visits an edge from person to neighbor, there are two cases.

If neighbor has no color yet, the algorithm gives it the opposite color from person. This satisfies the edge constraint for that edge.

If neighbor already has a color, the algorithm checks whether it equals color[person]. If the colors are equal, then the two people would be in the same group despite disliking each other. No valid bipartition can keep this coloring and satisfy the edge, so the algorithm returns false.

If no conflict is found, every checked dislike edge connects different colors.

The algorithm starts a traversal from every uncolored person, so it covers all connected components, not only the component containing person 1.

Therefore, if the algorithm returns true, every dislike pair has endpoints in different groups, so a valid bipartition exists.

If a valid bipartition exists, graph coloring with two colors is possible. The traversal only forces neighbors to have opposite colors, which is required by every valid bipartition. Since no odd-cycle conflict exists in a bipartite graph, the algorithm will never find two adjacent nodes with the same color. Therefore, it will return true.

Thus, the algorithm is correct.

Complexity

Let:

V = n
E = len(dislikes)

Implementation

from collections import deque

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 start in range(1, n + 1):
            if color[start] != 0:
                continue

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

            while queue:
                person = queue.popleft()

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

        return True

Code Explanation

We create an adjacency list with n + 1 slots:

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

The people are labeled from 1 to n, so index 0 is unused.

For each dislike pair, we add both directions:

graph[a].append(b)
graph[b].append(a)

This is an undirected graph.

The color array starts with all people uncolored:

color = [0] * (n + 1)

We scan all people:

for start in range(1, n + 1):

If a person already has a color, that person belongs to a component we have already processed.

If not, we start a BFS:

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

For every neighbor, if it has no color, we assign the opposite color:

color[neighbor] = -color[person]

If a neighbor already has the same color, the bipartition is impossible:

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

If the BFS finishes for every component without conflict, we return:

return True

Testing

def run_tests():
    s = Solution()

    assert s.possibleBipartition(
        4,
        [[1, 2], [1, 3], [2, 4]]
    ) is True

    assert s.possibleBipartition(
        3,
        [[1, 2], [1, 3], [2, 3]]
    ) is False

    assert s.possibleBipartition(
        5,
        [[1, 2], [2, 3], [3, 4], [4, 5], [1, 5]]
    ) is False

    assert s.possibleBipartition(
        4,
        []
    ) is True

    assert s.possibleBipartition(
        6,
        [[1, 2], [3, 4], [5, 6]]
    ) is True

    print("all tests passed")

run_tests()

Test meaning: