886. Possible Bipartition LeetCode Solution

In this guide, you will get 886. Possible Bipartition LeetCode Solution with the best time and space complexity. The solution to Possible Bipartition problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Possible Bipartition solution in C++
Possible Bipartition solution in Java
Possible Bipartition solution in Python
Additional Resources

886. Possible Bipartition LeetCode Solution image

Problem Statement of Possible Bipartition

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.

Complexity Analysis

Time Complexity: O(|V| + |E|)
Space Complexity: O(|V|)

886. Possible Bipartition LeetCode Solution in C++

enum Color { kWhite, kRed, kGreen };

class Solution {
 public:
  bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
    vector<vector<int>> graph(n + 1);
    vector<Color> colors(n + 1, Color::kWhite);

    for (const vector<int>& d : dislikes) {
      const int u = d[0];
      const int v = d[1];
      graph[u].push_back(v);
      graph[v].push_back(u);
    }

    // Reduce to 785. Is Graph Bipartite?
    for (int i = 1; i <= n; ++i)
      if (colors[i] == Color::kWhite &&
          !isValidColor(graph, i, colors, Color::kRed))
        return false;

    return true;
  }

 private:
  bool isValidColor(const vector<vector<int>>& graph, int u,
                    vector<Color>& colors, Color color) {
    // Always paint red for a white node.
    if (colors[u] != Color::kWhite)
      return colors[u] == color;

    colors[u] = color;  // Always paint the node with `color`.

    // All the children should have valid colors.
    for (const int v : graph[u])
      if (!isValidColor(graph, v, colors,
                        color == Color::kRed ? Color::kGreen : Color::kRed))
        return false;

    return true;
  }
};
/* code provided by PROGIEZ */

886. Possible Bipartition LeetCode Solution in Java

enum Color { kWhite, kRed, kGreen }

class Solution {
  public boolean possibleBipartition(int n, int[][] dislikes) {
    List<Integer>[] graph = new List[n + 1];
    Color[] colors = new Color[n + 1];
    Arrays.fill(colors, Color.kWhite);

    for (int i = 1; i <= n; ++i)
      graph[i] = new ArrayList<>();

    for (int[] d : dislikes) {
      final int u = d[0];
      final int v = d[1];
      graph[u].add(v);
      graph[v].add(u);
    }

    // Reduce to 785. Is Graph Bipartite?
    for (int i = 1; i <= n; ++i)
      if (colors[i] == Color.kWhite && !isValidColor(graph, i, colors, Color.kRed))
        return false;

    return true;
  }

  private boolean isValidColor(List<Integer>[] graph, int u, Color[] colors, Color color) {
    // Always paint red for a white node.
    if (colors[u] != Color.kWhite)
      return colors[u] == color;

    colors[u] = color; // Always paint the node with `color`.

    // All the children should have valid colors.
    for (final int v : graph[u])
      if (!isValidColor(graph, v, colors, color == Color.kRed ? Color.kGreen : Color.kRed))
        return false;

    return true;
  }
}
// code provided by PROGIEZ

886. Possible Bipartition LeetCode Solution in Python

from enum import Enum


class Color(Enum):
  kWhite = 0
  kRed = 1
  kGreen = 2


class Solution:
  def possibleBipartition(self, n: int, dislikes: list[list[int]]) -> bool:
    graph = [[] for _ in range(n + 1)]
    colors = [Color.kWhite] * (n + 1)

    for u, v in dislikes:
      graph[u].append(v)
      graph[v].append(u)

    # Reduce to 785. Is Graph Bipartite?
    def isValidColor(u: int, color: Color) -> bool:
      # Always paint red for a white node.
      if colors[u] != Color.kWhite:
        return colors[u] == color

      colors[u] = color  # Always paint the node with `color`.

      # All the children should have valid colors.
      childrenColor = Color.kRed if colors[u] == Color.kGreen else Color.kGreen
      return all(isValidColor(v, childrenColor) for v in graph[u])

    return all(colors[i] != Color.kWhite or isValidColor(i, Color.kRed)
               for i in range(1, n + 1))
 # code by PROGIEZ