Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using union-find strategy.
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 <= ndislikes are unique.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Union-Find
4 [[1,2],[1,3],[2,4]]
3 [[1,2],[1,3],[2,3]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #886: Possible Bipartition
class Solution {
private List<Integer>[] g;
private int[] color;
public boolean possibleBipartition(int n, int[][] dislikes) {
g = new List[n];
color = new int[n];
Arrays.setAll(g, k -> new ArrayList<>());
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) {
if (color[i] == 0) {
if (!dfs(i, 1)) {
return false;
}
}
}
return true;
}
private boolean dfs(int i, int c) {
color[i] = c;
for (int j : g[i]) {
if (color[j] == c) {
return false;
}
if (color[j] == 0 && !dfs(j, 3 - c)) {
return false;
}
}
return true;
}
}
// Accepted solution for LeetCode #886: Possible Bipartition
func possibleBipartition(n int, dislikes [][]int) bool {
g := make([][]int, n)
for _, e := range dislikes {
a, b := e[0]-1, e[1]-1
g[a] = append(g[a], b)
g[b] = append(g[b], a)
}
color := make([]int, n)
var dfs func(int, int) bool
dfs = func(i, c int) bool {
color[i] = c
for _, j := range g[i] {
if color[j] == c {
return false
}
if color[j] == 0 && !dfs(j, 3-c) {
return false
}
}
return true
}
for i, c := range color {
if c == 0 && !dfs(i, 1) {
return false
}
}
return true
}
# Accepted solution for LeetCode #886: Possible Bipartition
class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
def dfs(i, c):
color[i] = c
for j in g[i]:
if color[j] == c:
return False
if color[j] == 0 and not dfs(j, 3 - c):
return False
return True
g = defaultdict(list)
color = [0] * n
for a, b in dislikes:
a, b = a - 1, b - 1
g[a].append(b)
g[b].append(a)
return all(c or dfs(i, 1) for i, c in enumerate(color))
// Accepted solution for LeetCode #886: Possible Bipartition
impl Solution {
fn dfs(i: usize, v: usize, color: &mut Vec<usize>, g: &Vec<Vec<usize>>) -> bool {
color[i] = v;
for &j in (*g[i]).iter() {
if color[j] == color[i] || (color[j] == 0 && Self::dfs(j, v ^ 3, color, g)) {
return true;
}
}
false
}
pub fn possible_bipartition(n: i32, dislikes: Vec<Vec<i32>>) -> bool {
let n = n as usize;
let mut color = vec![0; n + 1];
let mut g = vec![Vec::new(); n + 1];
for d in dislikes.iter() {
let (i, j) = (d[0] as usize, d[1] as usize);
g[i].push(j);
g[j].push(i);
}
for i in 1..=n {
if color[i] == 0 && Self::dfs(i, 1, &mut color, &g) {
return false;
}
}
true
}
}
// Accepted solution for LeetCode #886: Possible Bipartition
function possibleBipartition(n: number, dislikes: number[][]): boolean {
const color = new Array(n + 1).fill(0);
const g = Array.from({ length: n + 1 }, () => []);
const dfs = (i: number, v: number) => {
color[i] = v;
for (const j of g[i]) {
if (color[j] === color[i] || (color[j] === 0 && dfs(j, 3 ^ v))) {
return true;
}
}
return false;
};
for (const [a, b] of dislikes) {
g[a].push(b);
g[b].push(a);
}
for (let i = 1; i <= n; i++) {
if (color[i] === 0 && dfs(i, 1)) {
return false;
}
}
return true;
}
Use this to step through a reusable interview workflow for this problem.
Track components with a list or adjacency matrix. Each union operation may need to update all n elements’ component labels, giving O(n) per union. For n union operations total: O(n²). Find is O(1) with direct lookup, but union dominates.
With path compression and union by rank, each find/union operation takes O(α(n)) amortized time, where α is the inverse Ackermann function — effectively constant. Space is O(n) for the parent and rank arrays. For m operations on n elements: O(m × α(n)) total.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.