Possible Bipartition

Medium
459.

Possible Bipartition

Possible Bipartition is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google and Meta interviews.

A group of n people labelled 1 through n must be split into two groups of any size. dislikes[i] = [a, b] means a and b refuse to be in the same group.

Return true if such a split is possible.

Example 1

Input
n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output
true
Explanation
Groups {1,4} and {2,3}.

Example 2

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

Example 3

Input
n = 1, dislikes = []
Output
true

Constraints

  • 1 <= n <= 30
  • 0 <= dislikes.length <= 60
  • 1 <= dislikes[i][0] < dislikes[i][1] <= n
  • There are no duplicate pairs.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} dislikes
 * @return {boolean}
 */
var possibleBipartition = function(n, dislikes) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Possible Bipartition — Solution in Python, Java & C++

Possible Bipartition solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Possible Bipartition is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google and Meta interviews.

Problem statement

A group of n people labelled 1 through n must be split into two groups of any size. dislikes[i] = [a, b] means a and b refuse to be in the same group.

Return true if such a split is possible.

Example 1

Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: Groups {1,4} and {2,3}.

Example 2

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

Example 3

Input: n = 1, dislikes = []
Output: true

Constraints

  • 1 <= n <= 30
  • 0 <= dislikes.length <= 60
  • 1 <= dislikes[i][0] < dislikes[i][1] <= n
  • There are no duplicate pairs.

Hints for Possible Bipartition

  1. Hint 1

    Build a graph where an edge means "must be apart" — the question is whether it is bipartite.

  2. Hint 2

    Two-colour it with BFS or DFS, giving each neighbour the opposite colour.

  3. Hint 3

    Start from every uncoloured person, since the dislike graph may be disconnected.

How to solve Possible Bipartition

Build the dislike graph and test whether it is bipartite by two-colouring with BFS.

Approach

  1. Adjacency list from dislikes.
  2. For each uncoloured person, BFS assigning opposite colours; fail on a same-colour neighbour.

Why it works

The two groups are the two colour classes; a valid split exists iff the graph has no odd cycle.

Complexity

  • Time — O(n + d)
  • Space — O(n + d)

Pitfalls

  • People are 1-indexed; size the arrays n + 1.

Reference solution

Python

from collections import deque

def possibleBipartition(n: int, dislikes) -> bool:
    adjacency = [[] for _ in range(n + 1)]
    for a, b in dislikes:
        adjacency[a].append(b)
        adjacency[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:
            node = queue.popleft()
            for nxt in adjacency[node]:
                if color[nxt] == 0:
                    color[nxt] = -color[node]
                    queue.append(nxt)
                elif color[nxt] == color[node]:
                    return False
    return True

Java

public static boolean possibleBipartition(int n, int[][] dislikes) {
    List<List<Integer>> adjacency = new ArrayList<>();
    for (int i = 0; i <= n; i++) adjacency.add(new ArrayList<>());
    for (int[] pair : dislikes) {
        adjacency.get(pair[0]).add(pair[1]);
        adjacency.get(pair[1]).add(pair[0]);
    }
    int[] color = new int[n + 1];
    for (int start = 1; start <= n; start++) {
        if (color[start] != 0) continue;
        color[start] = 1;
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(start);
        while (!queue.isEmpty()) {
            int node = queue.pollFirst();
            for (int next : adjacency.get(node)) {
                if (color[next] == 0) {
                    color[next] = -color[node];
                    queue.addLast(next);
                } else if (color[next] == color[node]) {
                    return false;
                }
            }
        }
    }
    return true;
}

C++

bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
    vector<vector<int>> adjacency(n + 1);
    for (const auto& pair : dislikes) {
        adjacency[pair[0]].push_back(pair[1]);
        adjacency[pair[1]].push_back(pair[0]);
    }
    vector<int> color(n + 1, 0);
    for (int start = 1; start <= n; start++) {
        if (color[start] != 0) continue;
        color[start] = 1;
        vector<int> queue;
        queue.push_back(start);
        size_t head = 0;
        while (head < queue.size()) {
            int node = queue[head++];
            for (int next : adjacency[node]) {
                if (color[next] == 0) {
                    color[next] = -color[node];
                    queue.push_back(next);
                } else if (color[next] == color[node]) {
                    return false;
                }
            }
        }
    }
    return true;
}

JavaScript

var possibleBipartition = function(n, dislikes) {
    const adjacency = [];
    for (let i = 0; i <= n; i++) adjacency.push([]);
    for (let i = 0; i < dislikes.length; i++) {
        adjacency[dislikes[i][0]].push(dislikes[i][1]);
        adjacency[dislikes[i][1]].push(dislikes[i][0]);
    }
    const color = [];
    for (let i = 0; i <= n; i++) color.push(0);
    for (let start = 1; start <= n; start++) {
        if (color[start] !== 0) continue;
        color[start] = 1;
        const queue = [start];
        let head = 0;
        while (head < queue.length) {
            const node = queue[head++];
            for (let i = 0; i < adjacency[node].length; i++) {
                const next = adjacency[node][i];
                if (color[next] === 0) {
                    color[next] = -color[node];
                    queue.push(next);
                } else if (color[next] === color[node]) {
                    return false;
                }
            }
        }
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)