algoadvance

Leetcode 886. Possible Bipartition

Problem Statement

Given a set of N people (numbered 1, 2, …, N), we would like to split everyone into two groups of any size. Each person may dislike some other people, and they should not be in the same group.

Formally, if dislikes[i] = [a, b], it means it is not allowed to put person a and person b in the same group.

Return true if and only if it is possible to split everyone into two groups in this way.

Clarifying Questions

  1. Can there be people who have no dislikes?
    • Yes, some people may have no dislikes.
  2. Is it guaranteed that the dislikes list will cover all N people?
    • No, it’s not guaranteed. Some people might not be mentioned in the dislikes list at all.
  3. Can the input dislikes list contain duplicate pairs?
    • Typically, it’s assumed that there are no duplicates in the dislikes list, as it complicates the problem without adding substantial benefit.

Strategy

To determine if the set of people can be split into two groups such that no two people in the same group dislike each other, we can model this as a bipartite graph problem. A graph is bipartite if we can color it using two colors without any two adjacent nodes having the same color.

Steps:

  1. Model the problem as a graph where each person is a node, and the dislikes between people are the edges.
  2. Use a coloring algorithm:
    • DFS (Depth First Search) or BFS (Breadth First Search) can be used to color the graph.
    • Attempt to color the graph using two colors.
  3. If we can color the graph without conflicts, return true. Otherwise, return false.

Code (Using DFS for Graph Coloring)

import java.util.ArrayList;
import java.util.List;

public class Solution {
    
    public boolean possibleBipartition(int N, int[][] dislikes) {
        // Initialize graph
        List<List<Integer>> graph = new ArrayList<>(N + 1);
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        // Build the adjacency list from the dislikes array
        for (int[] pair : dislikes) {
            int a = pair[0];
            int b = pair[1];
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        int[] color = new int[N + 1]; // 0: uncolored, 1: red, -1: blue
        
        // Try to color each node using DFS
        for (int i = 1; i <= N; i++) {
            if (color[i] == 0 && !dfs(graph, color, i, 1)) {
                return false;
            }
        }
        
        return true;
    }

    private boolean dfs(List<List<Integer>> graph, int[] color, int node, int currentColor) {
        color[node] = currentColor;
        
        for (int neighbor : graph.get(node)) {
            if (color[neighbor] == currentColor) {
                return false; // Same color on both sides, not bipartite
            }
            if (color[neighbor] == 0 && !dfs(graph, color, neighbor, -currentColor)) {
                return false; // Recur with the opposite color
            }
        }
        
        return true;
    }
}

Time Complexity

Thus, the overall time complexity is ( O(V + E) ).

This code efficiently determines if the given set of people can be partitioned according to the constraints using the DFS approach for graph coloring.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI