The O(n) Club: Possible Bipartition: Or, How to Split Your Frenemies into Two Drama-Free Camps

The O(n) Club: Possible Bipartition — Or, How to Split Your Frenemies into Two Drama-Free Camps

⚡ TL;DR

Split n people into two teams, so no sworn enemies end up on the same side—a classic case of coloring a graph and hoping you don’t see a triangle. The quick and dirty with Java:

// Color graph with DFS
int[] color = new int[n + 1];
for (int i = 1; i <= n; i++) {
    if (color[i] == 0 && !dfs(graph, color, i, 1)) return false;
}
return true;

🧠 How Devs Usually Mess This Up

Ah, the classics:

🔍 What’s Actually Going On

This is the anti-drama club algorithm: People are nodes, dislikes are edgy edges. If you can pick two colors so neighbors never clash, congrats: your graph (and friend group) is bipartite and peace reigns (for now).

When you (literally) can’t, it’s probably thanks to an odd-length cycle—think three folks with mutual beef. That’s a triangle of doom that breaks two-color harmony.

🛠️ PseudoCode

• Step 1: Build the adjacency list. Dislike is mutual, so add both ways.

  for each [a, b] in dislikes:
    graph[a].add(b);
    graph[b].add(a);

  No silent beef—everyone’s angst gets shared equally.

• Step 2: Create a color array for people (0 for unpainted, 1/-1 for club t-shirts).

  int[] color = new int[n + 1];

  Yup, index from 1 to match the people labels. Nobody likes an off-by-one bug at a party.

• Step 3: For every uncolored soul, paint with DFS.

  boolean dfs(int node, int paint) {
    color[node] = paint;
    for (int neighbor : graph[node]) {
      if (color[neighbor] == 0) {
        if (!dfs(neighbor, -paint)) return false;
      } else if (color[neighbor] == paint) {
        return false;
      }
    }
    return true;
  }

  If you clash colors with a neighbor—run for the hills (or just return false, whatever works).

• Step 4: Check every node because cliques can be sneaky.

  for (int i = 1; i <= n; i++) {
    if (color[i] == 0 && !dfs(i, 1)) return false;
  }

  Nobody gets left uncolored, not even the quiet ones.

💻 The Code

public boolean possibleBipartition(int n, int[][] dislikes) {
    List<Integer>[] graph = new ArrayList[n + 1];
    for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
    for (int[] pair : dislikes) {
        graph[pair[0]].add(pair[1]);
        graph[pair[1]].add(pair[0]);
    }
    int[] color = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        if (color[i] == 0 && !dfs(graph, color, i, 1)) return false;
    }
    return true;
}
 private boolean dfs(List<Integer>[] graph, int[] color, int node, int paint) {
    color[node] = paint;
    for (int neighbor : graph[node]) {
        if (color[neighbor] == 0) {
            if (!dfs(graph, color, neighbor, -paint)) return false;
        } else if (color[neighbor] == paint) {
            return false;
        }
    }
    return true;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Watch out for odd cycles—like a feuding trio. You can’t split them with only two sides.
• Your graph might be many islands (a.k.a. groups)—check them all or miss the introverts’ problems.
• Mind the indexes! Use n+1 for 1-based nodes or you’ll paint outside the lines (and your heap).
• O(n + e) and that’s it. Space and time—with DFS, code and coffee survive the largest drama club.

🧠 Interviewer Brain-Tattoo

“If your haters form an odd cycle, toss the paint brush and just split snacks instead.”