LeetCode 886: Possible Bipartition Solution

Master LeetCode problem 886 (Possible Bipartition), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

886. Possible Bipartition

Medium

Depth-First Search Breadth-First Search Union Find Graph

Problem Explanation

Explanation:

To solve this problem, we can use a graph coloring approach. We can create a graph where each person is a node, and an edge between two nodes represents a dislike relationship. We then try to color the nodes (people) with two colors such that no two connected nodes have the same color.

If we can successfully color all nodes with two colors without any conflicts, then it is possible to split everyone into two groups. If at any point we encounter a conflict where two connected nodes have the same color, then it is not possible to split them into two groups.

We can use a depth-first search (DFS) algorithm to traverse the graph and color the nodes. We start by assigning the color 0 to the first node and its disliked nodes with color 1, and vice versa. Then, we continue coloring the nodes by visiting each node and assigning the opposite color to its neighbors. If we encounter a conflict during this process, we return false. :

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 886 (Possible Bipartition)?

This page provides optimized solutions for LeetCode problem 886 (Possible Bipartition) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 886 (Possible Bipartition)?

The time complexity for LeetCode 886 (Possible Bipartition) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 886 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 886 in Java, C++, or Python.

Back to LeetCode Solutions