Possible Bipartition
MedPrompt
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] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.
Example 1:
Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: The first group has [1,4], and the second group has [2,3].Example 2:
Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
Explanation: We need at least 3 groups to divide them. We cannot put them in two groups.
Constraints:
1 <= n <= 20000 <= dislikes.length <= 104dislikes[i].length == 21 <= ai < bi <= n- All the pairs of
dislikesare unique.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach exhaustively explores all possible ways to partition the n people into two groups. It uses a recursive backtracking algorithm to try every possible assignment of a person to a group, pruning branches that lead to immediate conflicts.
Algorithm
- Create an adjacency list to represent the dislike relationships for quick lookups.\n- Create a
groupsarray to store the group assignment for each person (e.g., 1 for group A, 2 for group B).\n- Define a recursive functionsolve(personId)that tries to assign a group topersonId.\n- Base Case: IfpersonIdis greater thann, it means all people have been successfully assigned, so returntrue.\n- Recursive Step:\n - Try assigningpersonIdto group 1. Check if this conflicts with any neighbors ofpersonIdthat are already in group 1.\n - If it's a valid move, recursively callsolve(personId + 1). If the call returnstrue, a solution is found, so propagatetrue.\n - If not, try assigningpersonIdto group 2, performing a similar check and recursive call.\n - If neither assignment leads to a solution, backtrack by returningfalse.
Walkthrough
We define a recursive function that attempts to assign a group to each person, one by one, from 1 to n. For each person, we try placing them in group 1. If this placement doesn't conflict with any previously assigned disliked neighbors, we proceed recursively to the next person. If the recursive path fails, we backtrack and try placing the person in group 2. A solution is found if we can successfully assign a group to all n people. This method is conceptually straightforward but computationally expensive, as it may need to explore a number of possibilities that is exponential in n.\n\njava\nclass Solution {\n public boolean possibleBipartition(int n, int[][] dislikes) {\n List<Integer>[] adj = new ArrayList[n + 1];\n for (int i = 1; i <= n; i++) {\n adj[i] = new ArrayList<>();\n }\n for (int[] d : dislikes) {\n adj[d[0]].add(d[1]);\n adj[d[1]].add(d[0]);\n }\n int[] groups = new int[n + 1]; // 0: unassigned, 1: group A, 2: group B\n return solve(1, n, adj, groups);\n }\n\n private boolean solve(int personId, int n, List<Integer>[] adj, int[] groups) {\n if (personId > n) {\n return true;\n }\n\n // Try assigning to group 1\n if (isValid(personId, 1, adj, groups)) {\n groups[personId] = 1;\n if (solve(personId + 1, n, adj, groups)) {\n return true;\n }\n }\n\n // Try assigning to group 2\n if (isValid(personId, 2, adj, groups)) {\n groups[personId] = 2;\n if (solve(personId + 1, n, adj, groups)) {\n return true;\n }\n }\n \n groups[personId] = 0; // Backtrack\n return false;\n }\n\n private boolean isValid(int personId, int group, List<Integer>[] adj, int[] groups) {\n for (int neighbor : adj[personId]) {\n if (groups[neighbor] == group) {\n return false;\n }\n }\n return true;\n }\n}\n
Complexity
Time
O(2^n * n). In the worst case, we explore a significant portion of the 2^n possible assignments. For each assignment step, we may check up to n-1 neighbors.
Space
O(n + E) to store the adjacency list and O(n) for the recursion stack depth. `E` is the number of dislikes.
Trade-offs
Pros
Conceptually simple, directly modeling the problem of trying all possibilities.
Cons
Extremely inefficient with exponential time complexity, making it infeasible for the given constraints.
Does not handle disconnected components in a graph-native way.
This problem can be reframed as a graph coloring problem. We can represent the people as vertices and the dislike relationships as edges in a graph. The question then becomes: is this graph bipartite? A graph is bipartite if we can color its vertices with two colors such that no two adjacent vertices have the same color. DFS is a classic and efficient algorithm for this task.
Algorithm
- Build an adjacency list
adjfrom thedislikesarray.\n- Initialize acolorsarray (sizen+1) with a value indicating 'uncolored' (e.g., 0).\n- Iterate fromi = 1ton:\n - If personiis uncolored (colors[i] == 0):\n - Start a DFS fromiby calling a helper functiondfs(i, 1), attempting to coloriwith the first color.\n - Ifdfsreturnsfalse, a conflict was found, so the partition is impossible. Returnfalse.\n- If the loop completes, returntrue.\n- DFS helperdfs(node, color):\n - Color thenodewith the givencolor.\n - For eachneighborofnode:\n - Ifneighboris uncolored, recursively calldfs(neighbor, -color). If this call returnsfalse, propagatefalse.\n - Ifneighborhas the same color asnode, returnfalse.\n - Returntrueif no conflicts are found for thisnode.
Walkthrough
We first build an adjacency list to represent the graph. We also use a colors array to store the color of each vertex (person), with possible states like uncolored, color A, or color B. We iterate through all people to handle graphs that may have multiple disconnected components. If a person is uncolored, we start a DFS traversal from them. During the DFS, we color the current vertex and then visit its neighbors. If a neighbor is uncolored, we recursively call DFS on it with the opposite color. If a neighbor is already colored and has the same color as the current vertex, we have detected an odd-length cycle, which means the graph is not bipartite, and we return false. If all components can be two-colored without conflict, we return true.\n\njava\nclass Solution {\n public boolean possibleBipartition(int n, int[][] dislikes) {\n List<Integer>[] adj = new ArrayList[n + 1];\n for (int i = 1; i <= n; i++) {\n adj[i] = new ArrayList<>();\n }\n for (int[] d : dislikes) {\n adj[d[0]].add(d[1]);\n adj[d[1]].add(d[0]);\n }\n\n int[] colors = new int[n + 1]; // 0: uncolored, 1: color A, -1: color B\n for (int i = 1; i <= n; i++) {\n if (colors[i] == 0) {\n if (!dfs(i, 1, colors, adj)) {\n return false;\n }\n }\n }\n return true;\n }\n\n private boolean dfs(int node, int color, int[] colors, List<Integer>[] adj) {\n colors[node] = color;\n for (int neighbor : adj[node]) {\n if (colors[neighbor] == 0) {\n if (!dfs(neighbor, -color, colors, adj)) {\n return false;\n }\n } else if (colors[neighbor] == color) {\n return false;\n }\n }\n return true;\n }\n}\n
Complexity
Time
O(n + E), where `n` is the number of people and `E` is `dislikes.length`. We visit each vertex and edge once.
Space
O(n + E) for the adjacency list, `colors` array, and recursion stack.
Trade-offs
Pros
Highly efficient with linear time complexity.
Correctly handles disconnected graphs.
Standard and robust algorithm for bipartiteness checking.
Cons
Requires understanding of graph theory and DFS.
Recursive implementation could theoretically cause a stack overflow on extremely deep graphs, though unlikely with given constraints.
This is another optimal approach that treats the problem as checking for graph bipartiteness. It uses Breadth-First Search (BFS) instead of DFS. BFS explores the graph layer by layer, which is also perfectly suited for two-coloring.
Algorithm
- Build an adjacency list
adjfrom thedislikesarray.\n- Initialize acolorsarray (sizen+1) with a value indicating 'uncolored' (e.g., 0).\n- Iterate fromi = 1ton:\n - If personiis uncolored (colors[i] == 0):\n - Create a queue, addito it, and coloriwith the first color (colors[i] = 1).\n - While the queue is not empty:\n - Dequeue a personu.\n - For eachneighborvofu:\n - Ifvis uncolored, color it with the opposite color (-colors[u]) and enqueue it.\n - Ifvhas the same color asu, returnfalse.\n- If the loop completes without returningfalse, returntrue.
Walkthrough
Like the DFS approach, we start by building an adjacency list and a colors array. We iterate through all people to ensure all connected components are checked. For each uncolored person, we initiate a BFS. We add the person to a queue and assign them an initial color. Then, we enter a loop that continues as long as the queue is not empty. In each iteration, we dequeue a person u and examine their neighbors. If a neighbor v is uncolored, we assign it the opposite color of u and enqueue it. If v is already colored and has the same color as u, a conflict is found, and we immediately know a valid partition is impossible.\n\njava\nclass Solution {\n public boolean possibleBipartition(int n, int[][] dislikes) {\n List<Integer>[] adj = new ArrayList[n + 1];\n for (int i = 1; i <= n; i++) {\n adj[i] = new ArrayList<>();\n }\n for (int[] d : dislikes) {\n adj[d[0]].add(d[1]);\n adj[d[1]].add(d[0]);\n }\n\n int[] colors = new int[n + 1]; // 0: uncolored, 1: color A, -1: color B\n Queue<Integer> queue = new LinkedList<>();\n\n for (int i = 1; i <= n; i++) {\n if (colors[i] == 0) {\n queue.offer(i);\n colors[i] = 1;\n while (!queue.isEmpty()) {\n int u = queue.poll();\n for (int v : adj[u]) {\n if (colors[v] == 0) {\n colors[v] = -colors[u];\n queue.offer(v);\n } else if (colors[v] == colors[u]) {\n return false;\n }\n }\n }\n }\n }\n return true;\n }\n}\n
Complexity
Time
O(n + E), where `n` is the number of people and `E` is `dislikes.length`. Each vertex and edge is processed once.
Space
O(n + E) for the adjacency list, `colors` array, and the queue. The queue can hold up to O(n) vertices in the worst case.
Trade-offs
Pros
Optimal linear time complexity, same as DFS.
Iterative approach avoids any risk of stack overflow errors.
Also correctly handles disconnected graphs.
Cons
Requires understanding of graph theory and BFS.
The code can be slightly more verbose than the recursive DFS version.
Solutions
Solution
class Solution {private int[] p;public boolean possibleBipartition(int n, int[][] dislikes) { p = new int[n]; List<Integer>[] g = new List[n]; Arrays.setAll(g, k->new ArrayList<>()); for (int i = 0; i < n; ++i) { p[i] = i; } for (var e : dislikes) { int a = e[0] - 1, b = e[1] - 1; g[a].add(b); g[b].add(a); } for (int i = 0; i < n; ++i) { for (int j : g[i]) { if (find(i) == find(j)) { return false; } p[find(j)] = find(g[i].get(0)); } } return true; }private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; }}class Solution {public: bool possibleBipartition(int n, vector<vector<int>> &dislikes) { vector<int> p(n); iota(p.begin(), p.end(), 0); unordered_map<int, vector<int>> g; for (auto &e : dislikes) { int a = e[0] - 1, b = e[1] - 1; g[a].push_back(b); g[b].push_back(a); } function<int(int)> find = [&](int x) -> int { if (p[x] != x) p[x] = find(p[x]); return p[x]; }; for (int i = 0; i < n; ++i) { for (int j : g[i]) { if (find(i) == find(j)) return false; p[find(j)] = find(g[i][0]); } } return true; }};class Solution: def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] g = defaultdict(list) for a, b in dislikes: a, b = a - 1, b - 1 g[a]. append(b) g[b]. append(a) p = list(range(n)) for i in range(n): for j in g[i]: if find(i) == find(j): return False p[find(j)] = find(g[i][0]) return TrueVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.