We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Possible Bipartition

Number: 922

Difficulty: Medium

Paid? No

Companies: LinkedIn, Amazon, Uber, Google, TikTok, Arcesium, Microsoft

Problem Description

Given n people labeled from 1 to n and an array of pairs representing mutual dislikes, determine if it is possible to split the people into two groups such that no pair of people who dislike each other end up in the same group. This is equivalent to checking if the graph formed by people (nodes) and dislikes (edges) is bipartite.

Key Insights

  • Model the problem as a graph where each person is a node and each dislike relationship is an undirected edge.
  • Check whether the graph is bipartite by trying to color the graph with two different colors.
  • A graph is bipartite if and only if it is possible to assign one of two colors to each vertex such that no two adjacent vertices share the same color.
  • Use either Depth-First Search (DFS), Breadth-First Search (BFS), or Union Find to solve the problem.
  • Consider that the graph may be disconnected, so each component must be checked.

Space and Time Complexity

Time Complexity: O(n + m) where n is the number of people (nodes) and m is the number of dislike pairs (edges).
Space Complexity: O(n + m) due to the graph representation and additional space for the color mappings.

Solution

We first build an adjacency list to represent the graph. Then, we perform a graph traversal (using DFS or BFS) to try to color the graph using two colors. If we encounter a conflict (i.e., two adjacent nodes are assigned the same color), we return false. If we are able to successfully color all connected components of the graph, then a bipartition is possible, and we return true. Key data structures include:

  • An adjacency list (often a dictionary or array of lists)
  • A color map (such as an array or dictionary) to keep track of group assignments during traversal

Code Solutions

# Python solution using DFS

def possibleBipartition(n, dislikes):
    # Build graph as an adjacency list
    graph = {i: [] for i in range(1, n + 1)}
    for a, b in dislikes:
        graph[a].append(b)
        graph[b].append(a)
    
    # Dictionary to store colors for each node: 1 or -1
    colors = {}

    def dfs(node, color):
        # Assign the current node the given color
        colors[node] = color
        # Traverse all adjacent nodes
        for neighbor in graph[node]:
            # If neighbor is already colored
            if neighbor in colors:
                # If neighbor has the same color, bipartition not possible
                if colors[neighbor] == color:
                    return False
            else:
                # Recursively assign opposite color to neighbor
                if not dfs(neighbor, -color):
                    return False
        return True

    # Check all nodes in case graph is disconnected
    for person in range(1, n + 1):
        # If person not visited, start DFS with color 1
        if person not in colors:
            if not dfs(person, 1):
                return False
    return True

# Example usage:
# print(possibleBipartition(4, [[1,2],[1,3],[2,4]]))  # Expected output: True
← Back to All Questions