Code Implementation

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        from collections import defaultdict, deque
        graph = defaultdict(list)
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)
        color = {}
        for node in range(1, n+1):
            if node not in color:
                queue = deque()
                queue.append((node, 0))
                while queue:
                    curr, c = queue.popleft()
                    if curr in color:
                        if color[curr] != c:
                            return False
                        continue
                    color[curr] = c
                    for nei in graph[curr]:
                        queue.append((nei, 1-c))
        return True
      

class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        vector<vector<int>> graph(n+1);
        for (auto &d : dislikes) {
            graph[d[0]].push_back(d[1]);
            graph[d[1]].push_back(d[0]);
        }
        vector<int> color(n+1, -1);
        for (int i = 1; i <= n; ++i) {
            if (color[i] == -1) {
                queue<int> q;
                q.push(i);
                color[i] = 0;
                while (!q.empty()) {
                    int u = q.front(); q.pop();
                    for (int v : graph[u]) {
                        if (color[v] == -1) {
                            color[v] = 1 - color[u];
                            q.push(v);
                        } else if (color[v] == color[u]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
};
      

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; ++i) graph.add(new ArrayList<>());
        for (int[] d : dislikes) {
            graph.get(d[0]).add(d[1]);
            graph.get(d[1]).add(d[0]);
        }
        int[] color = new int[n+1];
        Arrays.fill(color, -1);
        for (int i = 1; i <= n; ++i) {
            if (color[i] == -1) {
                Queue<Integer> q = new LinkedList<>();
                q.offer(i);
                color[i] = 0;
                while (!q.isEmpty()) {
                    int u = q.poll();
                    for (int v : graph.get(u)) {
                        if (color[v] == -1) {
                            color[v] = 1 - color[u];
                            q.offer(v);
                        } else if (color[v] == color[u]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}
      

var possibleBipartition = function(n, dislikes) {
    const graph = Array.from({length: n+1}, () => []);
    for (const [u, v] of dislikes) {
        graph[u].push(v);
        graph[v].push(u);
    }
    const color = new Array(n+1).fill(-1);
    for (let i = 1; i <= n; ++i) {
        if (color[i] === -1) {
            const queue = [i];
            color[i] = 0;
            while (queue.length) {
                const u = queue.shift();
                for (const v of graph[u]) {
                    if (color[v] === -1) {
                        color[v] = 1 - color[u];
                        queue.push(v);
                    } else if (color[v] === color[u]) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
};
      

Problem Description

You are given n people, labeled from 1 to n. Some pairs of people dislike each other, given as a list dislikes, where each dislikes[i] = [a, b] means person a and person b dislike each other.

The task is to determine if it is possible to split all n people into two groups such that:

• Each person belongs to exactly one group.
• No pair of people who dislike each other are in the same group.

Key constraints:

• Each pair in dislikes is unique.
• Each person can appear in multiple pairs.
• There may be disconnected groups of people.
• You need to return true if such a bipartition is possible, false otherwise.

Thought Process

At first glance, this problem looks like a complex grouping or partitioning challenge. A brute-force approach might try every possible way to assign people to two groups, but this quickly becomes infeasible as the number of people grows.

Upon closer inspection, the problem is equivalent to checking if the graph formed by the dislikes pairs is bipartite. In a bipartite graph, the nodes can be colored with two colors such that no two adjacent nodes have the same color. Here, people are nodes, and a dislike is an edge.

This realization shifts our approach from brute-force partitioning to a classic graph coloring problem. Instead of checking every possible split, we can try to color the graph using two colors and see if any conflicts arise.

If we ever find two connected nodes (i.e., two people who dislike each other) that must have the same color, we know a bipartition is impossible.

Solution Approach

To solve this problem efficiently, we use a graph coloring technique:

1. Build the Graph:
   • Create an adjacency list where each person points to those they dislike.
2. Initialize Color Assignments:
   • Use a color array or dictionary to keep track of which group (color) each person is assigned to. Unassigned people have a default value (e.g., -1 or None).
3. Traverse Each Component:
   • Since the graph might be disconnected, loop through all people. For each uncolored person, start a BFS or DFS to attempt coloring their component.
4. Color the Graph:
   • For each person, assign a color (0 or 1). For each neighbor (person they dislike), assign the opposite color. If a neighbor is already colored with the same color, return false.
5. If No Conflicts:
   • If you finish coloring the whole graph without conflicts, return true. This means a bipartition is possible.

We use BFS (queue) for this explanation, but DFS works similarly. A hash map or array is used for colors because lookups and updates are O(1).

Example Walkthrough

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

1. Graph Construction:
   • 1 dislikes 2 and 3
   • 2 dislikes 1 and 4
   • 3 dislikes 1
   • 4 dislikes 2
2. Coloring:
   • Start with person 1, assign color 0.
   • Person 1's neighbors: 2 and 3. Assign both color 1.
   • Person 2's neighbors: 1 (already color 0, OK), 4 (assign color 0).
   • Person 3's neighbor: 1 (already color 0, OK).
   • Person 4's neighbor: 2 (already color 1, OK).
3. No conflicts found:
   • We successfully colored the graph. So, return true.

If at any point we tried to assign the same color to two people who dislike each other, we would return false.

Time and Space Complexity

• Brute-force approach:
  • Would try all possible groupings: O(2ⁿ) time, which is infeasible for large n.
• Optimized BFS/DFS coloring approach:
  • Time complexity: O(N + E), where N is the number of people and E is the number of dislike pairs. Each node and edge is visited at most once.
  • Space complexity: O(N + E) for the adjacency list and color assignments.

This is efficient and works well for the problem constraints.

Summary

The key insight is recognizing that the problem is equivalent to checking if a graph is bipartite. Instead of brute-force partitioning, we use BFS or DFS to color the graph and check for conflicts. This approach is efficient, elegant, and leverages classic graph theory to solve what initially seems like a complex grouping problem.