886. Possible Bipartition (Medium)

Problem

Given n people (labeled 1 to n) and a list of dislikes where dislikes[i] = [a, b] means person a and person b cannot be in the same group, determine if it is possible to split everyone into two groups such that no two people who dislike each other are in the same group.

Example

n = 4, dislikes = [[1,2],[1,3],[2,4]] → True (group A: 4, group B: 3)
n = 3, dislikes = [[1,2],[1,3],[2,3]] → False (triangle: 1,2,3 all dislike each other)
n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]] → False (odd cycle of length 5)

LeetCode 886 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach: Build dislikes graph, then check bipartiteness

This is exactly the bipartite check from problem 785, applied to the dislikes relationship. Two people who dislike each other must be in different groups, which is the same constraint as “adjacent nodes must have different colors.” So: build an undirected graph from dislikes, then run BFS 2-coloring.

from collections import defaultdict, deque

def possible_bipartition(n, dislikes):
    graph = defaultdict(list)                              # L1: O(e) adjacency list
    for a, b in dislikes:                                  # L2: O(e) build undirected graph
        graph[a].append(b)                                 # L3: O(1) edge a->b
        graph[b].append(a)                                 # L4: O(1) edge b->a

    color = {}                                             # L5: person -> color (0 or 1)

    for start in range(1, n + 1):                          # L6: handle disconnected components
        if start in color:
            continue                                       # L7: skip already-colored nodes
        color[start] = 0                                   # L8: O(1) seed color
        q = deque([start])                                 # L9: O(1) seed queue

        while q:                                           # L10: BFS loop
            person = q.popleft()                           # L11: O(1) dequeue
            for neighbor in graph[person]:                 # L12: O(deg) check neighbors
                if neighbor not in color:
                    color[neighbor] = 1 - color[person]   # L13: O(1) assign opposite color
                    q.append(neighbor)                     # L14: O(1) enqueue
                elif color[neighbor] == color[person]:
                    return False                           # L15: O(1) conflict, odd cycle

    return True                                            # L16: O(1) no conflict found

function possibleBipartition(n: number, dislikes: number[][]): boolean {
    const graph: number[][] = Array.from({ length: n + 1 }, () => []);
    for (const [a, b] of dislikes) {                       // L2: O(e) build undirected graph
        graph[a].push(b);                                  // L3: O(1) edge a->b
        graph[b].push(a);                                  // L4: O(1) edge b->a
    }

    const color = new Array(n + 1).fill(-1);               // L5: person -> color, -1 = unvisited

    for (let start = 1; start <= n; start++) {             // L6: handle disconnected components
        if (color[start] !== -1) continue;                 // L7: skip already-colored nodes
        color[start] = 0;                                  // L8: O(1) seed color
        const q: number[] = [start];                       // L9: O(1) seed queue
        let head = 0;

        while (head < q.length) {                          // L10: BFS loop
            const person = q[head++];                      // L11: O(1) dequeue
            for (const neighbor of graph[person]) {        // L12: O(deg) check neighbors
                if (color[neighbor] === -1) {
                    color[neighbor] = 1 - color[person];   // L13: O(1) assign opposite color
                    q.push(neighbor);                      // L14: O(1) enqueue
                } else if (color[neighbor] === color[person]) {
                    return false;                          // L15: O(1) conflict, odd cycle
                }
            }
        }
    }
    return true;                                           // L16: O(1) no conflict found
}

final class Solution {
    func possibleBipartition(_ n: Int, _ dislikes: [[Int]]) -> Bool {
        var graph = Array(repeating: [Int](), count: n + 1)
        for edge in dislikes { graph[edge[0]].append(edge[1]); graph[edge[1]].append(edge[0]) }
        var color = Array(repeating: 0, count: n + 1)
        for start in 1...n where color[start] == 0 {
            var queue = [start], head = 0; color[start] = 1
            while head < queue.count {
                let person = queue[head]; head += 1
                for next in graph[person] {
                    if color[next] == 0 { color[next] = -color[person]; queue.append(next) }
                    else if color[next] == color[person] { return false }
                }
            }
        }
        return true
    }
}

Where the time goes, line by line

Variables: n = number of people, e = number of dislikes pairs.

Line	Per-call cost	Times executed	Contribution
L2 (build graph)	$O(1)$ per edge	e	$O(e)$
L6 (outer loop)	$O(1)$	n	$O(n)$
L11 (dequeue)	$O(1)$	once per person	$O(n)$
L12 (neighbor scan)	$O(deg)$	once per person	$O(n + e)$ ← dominates
L13, L14 (color + enqueue)	$O(1)$	once per unvisited neighbor	$O(n)$

Complexity

Time: $O(n + e)$ , driven by L12 (each edge examined twice, each node dequeued once).
Space: $O(n + e)$ for the adjacency list (L1) and color map (L5).

Connection to 785

This problem is structurally identical to Is Graph Bipartite? (785). The only difference is the graph representation: 785 gives an adjacency list directly, while 886 gives an edge list that you must convert first. The BFS 2-coloring logic is unchanged.

Dislikes: [[1,2],[1,3],[2,4]]

Graph built (undirected):
  1 -- 2
  |    |
  3    4

BFS from 1: color[1]=0, color[2]=1, color[3]=1
  from 2: color[4]=0
  Check: no conflicts -> True
  Groups: {1,4} vs {2,3}

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Step	Cost
Build adjacency list	$O(e)$
BFS 2-coloring	$O(n + e)$
Total	$O(n + e)$

from collections import defaultdict, deque

def possible_bipartition(n, dislikes):
    graph = defaultdict(list)
    for a, b in dislikes:
        graph[a].append(b)
        graph[b].append(a)

    color = {}

    for start in range(1, n + 1):
        if start in color:
            continue
        color[start] = 0
        q = deque([start])
        while q:
            person = q.popleft()
            for neighbor in graph[person]:
                if neighbor not in color:
                    color[neighbor] = 1 - color[person]
                    q.append(neighbor)
                elif color[neighbor] == color[person]:
                    return False

    return True

def _run_tests():
    # Example 1: possible split
    assert possible_bipartition(4, [[1,2],[1,3],[2,4]]) == True

    # Example 2: triangle, impossible
    assert possible_bipartition(3, [[1,2],[1,3],[2,3]]) == False

    # Example 3: odd cycle of 5
    assert possible_bipartition(5, [[1,2],[2,3],[3,4],[4,5],[1,5]]) == False

    # No dislikes: trivially possible
    assert possible_bipartition(4, []) == True

    # Two isolated groups that are each bipartite
    assert possible_bipartition(4, [[1,2],[3,4]]) == True

    # Single person
    assert possible_bipartition(1, []) == True

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function possibleBipartition(n: number, dislikes: number[][]): boolean {
    const graph: number[][] = Array.from({ length: n + 1 }, () => []);
    for (const [a, b] of dislikes) { graph[a].push(b); graph[b].push(a); }

    const color = new Array(n + 1).fill(-1);
    for (let start = 1; start <= n; start++) {
        if (color[start] !== -1) continue;
        color[start] = 0;
        const q: number[] = [start];
        let head = 0;
        while (head < q.length) {
            const person = q[head++];
            for (const neighbor of graph[person]) {
                if (color[neighbor] === -1) { color[neighbor] = 1 - color[person]; q.push(neighbor); }
                else if (color[neighbor] === color[person]) return false;
            }
        }
    }
    return true;
}

console.assert(possibleBipartition(4, [[1,2],[1,3],[2,4]]) === true);
console.assert(possibleBipartition(3, [[1,2],[1,3],[2,3]]) === false);
console.assert(possibleBipartition(5, [[1,2],[2,3],[3,4],[4,5],[1,5]]) === false);
console.assert(possibleBipartition(4, []) === true);
console.assert(possibleBipartition(4, [[1,2],[3,4]]) === true);
console.assert(possibleBipartition(1, []) === true);
console.log("all tests pass");

Is Graph Bipartite?, identical algorithm on a directly given adjacency list
Number of Provinces, connected components with DFS/Union-Find

Graph Traversal, the visited set model for exploring nodes and edges without repetition.
BFS, the level order frontier pattern for shortest unweighted distance and wave expansion.

886. Possible Bipartition (Medium)

Problem

Try it yourself

Approach: Build dislikes graph, then check bipartiteness

Connection to 785

Summary

Test cases

Related topics

Related concepts