Scale Engineer

Possible Bipartition

Med
#0840Time: 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.5 companies
Algorithms
Depth-First SearchBreadth-First SearchUnion Find
Data structures
Graph
Companies
SamsungCoupangPinterestArcesium

Prompt

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 <= 2000
  • 0 <= dislikes.length <= 104
  • dislikes[i].length == 2
  • 1 <= ai < bi <= n
  • All the pairs of dislikes are 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 groups array to store the group assignment for each person (e.g., 1 for group A, 2 for group B).\n- Define a recursive function solve(personId) that tries to assign a group to personId.\n- Base Case: If personId is greater than n, it means all people have been successfully assigned, so return true.\n- Recursive Step:\n - Try assigning personId to group 1. Check if this conflicts with any neighbors of personId that are already in group 1.\n - If it's a valid move, recursively call solve(personId + 1). If the call returns true, a solution is found, so propagate true.\n - If not, try assigning personId to group 2, performing a similar check and recursive call.\n - If neither assignment leads to a solution, backtrack by returning false.

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\n

java\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.

Solutions

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];  }}

Video 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.

← Previous

Previous problem

Next →

Next problem