Possible Bipartition - Practice Coding Problems

Possible Bipartition - Problem

We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group.

Given the integer n and the array dislikes where dislikes[i] = [aᵢ, bᵢ] indicates that the person labeled aᵢ does not like the person labeled bᵢ, return true if it is possible to split everyone into two groups in this way.

Input & Output

Example 1 — Basic Bipartite Case

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

› Output: true

💡 Note: Group 0: {1,4}, Group 1: {2,3}. Person 1 dislikes 2 and 3 (different groups), person 2 dislikes 4 (different groups). All constraints satisfied.

Example 2 — Non-bipartite Case

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

› Output: false

💡 Note: This forms a triangle where everyone dislikes everyone else. Impossible to split into two groups without putting two people who dislike each other in the same group.

Example 3 — No Constraints

$ Input: n = 5, dislikes = []

› Output: true

💡 Note: No dislikes means everyone can go in any group. We can put anyone in group 0 and anyone in group 1.

Constraints

1 ≤ n ≤ 2000
0 ≤ dislikes.length ≤ 10⁴
dislikes[i].length == 2
1 ≤ a_i < b_i ≤ n
All pairs in dislikes are distinct

Visualization

Tap to expand

Understanding the Visualization

Input

n people and list of dislike pairs

Model as Graph

Create graph where edges represent dislikes

Check Bipartite

Use graph coloring to see if 2-group split is possible

Key Takeaway

🎯 Key Insight: A group can be split into two non-conflicting parts if and only if the dislike graph is bipartite

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is recognizing this as a graph bipartition problem. Model people as nodes and dislikes as edges, then check if the graph can be 2-colored using DFS/BFS. Best approach is DFS/BFS graph coloring with Time: O(n + m), Space: O(n + m).

Common Approaches

Approach	Time	Space	Notes
✓ BFS Graph Coloring	O(n + m)	O(n + m)	Use BFS to check if the dislike graph can be 2-colored
Brute Force - Try All Combinations	O(2^n × m)	O(n)	Generate all possible ways to split n people into two groups
DFS Graph Coloring	O(n + m)	O(n + m)	Build graph from dislikes and use DFS to check if it's 2-colorable

BFS Graph Coloring — Algorithm Steps

Build adjacency list from dislikes
For each unvisited person, start BFS
Use queue to assign alternating colors level by level
Return false if color conflict detected

Visualization

Tap to expand

Step-by-Step Walkthrough

Start BFS

Begin from unvisited person, assign to group 0

Process Neighbors

Add all neighbors to queue with opposite color

Continue Levels

Process each level ensuring no color conflicts

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool bfs(int** graph, int* graphSizes, int* colors, int start) {
    int queue[1000], front = 0, rear = 0;
    queue[rear++] = start;
    colors[start] = 0;
    
    while (front < rear) {
        int person = queue[front++];
        
        for (int i = 0; i < graphSizes[person]; i++) {
            int neighbor = graph[person][i];
            if (colors[neighbor] == colors[person]) {
                return false; // Same color conflict
            }
            if (colors[neighbor] == -1) {
                colors[neighbor] = 1 - colors[person];
                queue[rear++] = neighbor;
            }
        }
    }
    return true;
}

bool solution(int n, int dislikes[][2], int dislikesSize) {
    // Build adjacency list
    int** graph = (int**)malloc((n + 1) * sizeof(int*));
    int* graphSizes = (int*)calloc(n + 1, sizeof(int));
    
    for (int i = 0; i <= n; i++) {
        graph[i] = (int*)malloc(n * sizeof(int));
    }
    
    for (int i = 0; i < dislikesSize; i++) {
        int a = dislikes[i][0], b = dislikes[i][1];
        graph[a][graphSizes[a]++] = b;
        graph[b][graphSizes[b]++] = a;
    }
    
    // Colors: -1 = unvisited, 0 = group 0, 1 = group 1
    int* colors = (int*)malloc((n + 1) * sizeof(int));
    for (int i = 0; i <= n; i++) {
        colors[i] = -1;
    }
    
    // Process all connected components
    bool result = true;
    for (int i = 1; i <= n; i++) {
        if (colors[i] == -1) {
            if (!bfs(graph, graphSizes, colors, i)) {
                result = false;
                break;
            }
        }
    }
    
    // Cleanup
    for (int i = 0; i <= n; i++) {
        free(graph[i]);
    }
    free(graph);
    free(graphSizes);
    free(colors);
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %s", line);
    
    // Parse dislikes array manually
    int dislikes[1000][2];
    int dislikesSize = 0;
    
    if (strcmp(line, "[]") == 0) {
        printf("true\n");
        return 0;
    }
    
    char* ptr = line + 1; // Skip [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            dislikes[dislikesSize][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            dislikes[dislikesSize][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            dislikesSize++;
        }
        ptr++;
    }
    
    bool result = solution(n, dislikes, dislikesSize);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Each person and dislike edge visited once during BFS traversal

✓ Linear Growth

Space Complexity

O(n + m)

Adjacency list O(n + m), BFS queue stores at most O(n) people

⚡ Linearithmic Space

87.7K Views

Medium Frequency

~25 min Avg. Time

2.3K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS Graph Coloring — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler