Jobs

Interviews

Discussions

Possible Bipartition

Medium

Asked by:

14 views

Topics:

GraphsDepth-First SearchBreadth-First Search

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] = [a_i, b_i] indicates that the person labeled a_i does not like the person labeled b_i, 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 <= 10⁴
dislikes[i].length == 2
1 <= a_i < b_i <= n
All the pairs of dislikes are unique.

Possible Bipartition

Medium

Asked by:

14 views

Topics:

GraphsDepth-First SearchBreadth-First Search

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.

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 <= 10⁴
dislikes[i].length == 2
1 <= a_i < b_i <= n
All the pairs of dislikes are unique.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the range of values for 'n' and the number of dislikes?
Is an empty dislikes array considered a valid bipartition?
If it's impossible to form a bipartition, what should the function return? (e.g., false, null, throw an exception)?
Can a person dislike themselves? (i.e., can we have entries like [1, 1] in the dislikes array)?
Does the input 'dislikes' guarantee that the person numbers are within the range [1, n], or might they be out of bounds?

Brute Force Solution

Approach

The brute force approach to this problem is like trying to divide a group of people into two teams where some people don't get along. We will try every single possible team combination to see if any works.

Here's how the algorithm would work step-by-step:

Start by assigning the first person to team A.
Then, try assigning the second person to team A, and then to team B. For each of these options, continue...
For the third person, try assigning them to team A, and then to team B. Again, for each of these options, continue...
Keep doing this for every single person, trying to put them in either team A or team B.
Each time you assign someone to a team, check if they are in the same team as someone they don't get along with. If they are, this team setup doesn't work, so discard it.
If you manage to assign everyone to a team without anyone who dislikes each other ending up on the same team, then you've found a valid way to split the group.
Keep track of whether you find at least one valid way to split the group after exploring all the possibilities. If you do, then it's possible to split the group; otherwise, it's not.

Code Implementation

def possible_bipartition(number_of_people, dislikes):
    team_assignments = [0] * (number_of_people + 1)
    is_bipartite = False

    def backtrack(person_index):
        nonlocal is_bipartite

        # Base case: all people have been assigned to a team
        if person_index == number_of_people + 1:
            is_bipartite = True
            return

        # Try assigning the current person to team 1 or team 2
        for team in [1, 2]:
            team_assignments[person_index] = team

            # Check if the current assignment is valid
            is_valid = True
            for person_one, person_two in dislikes:
                if person_one == person_index:

                    # Ensure disliked people are not on the same team
                    if team_assignments[person_one] == team_assignments[person_two]:
                        is_valid = False
                        break
                elif person_two == person_index:
                    # Ensure disliked people are not on the same team
                    if team_assignments[person_one] == team_assignments[person_two]:
                        is_valid = False
                        break

            # If the current assignment is valid, continue exploring
            if is_valid:
                backtrack(person_index + 1)

            # If a solution is found, stop exploring other branches
            if is_bipartite:
                return

            team_assignments[person_index] = 0

    # Start assigning people to teams from person 1
    backtrack(1)

    # Determine whether there is a valid split
    return is_bipartite

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n * m) – The brute force approach involves trying all possible assignments of n people into two teams. For each person, there are two choices (team A or team B), leading to 2^n possible team combinations. For each of these combinations, we iterate through the dislikes list of size m (number of dislikes) to check if any conflicting pairs are in the same team. Therefore, the time complexity is O(2^n * m), where n is the number of people and m is the size of the dislikes list (number of edges).

Space Complexity

O(N) – The brute force approach explores all possible team assignments using recursion. In the worst-case scenario, where no conflicts are found early on, the recursive calls can reach a depth of N, where N is the number of people. Each recursive call adds a new frame to the call stack to store the current team assignments, resulting in a maximum call stack size of N. Thus, the auxiliary space used by the recursion stack is proportional to N, giving us a space complexity of O(N).

Optimal Solution

Approach

The problem asks if a group of people can be divided into two teams where people who dislike each other are on different teams. The best approach is to go through the relationships one by one and assign people to teams while ensuring that no conflicting assignments are made. If a conflict arises at any point, it's impossible to divide the group as requested.

Here's how the algorithm would work step-by-step:

Imagine each person as a node and each dislike as an edge connecting the nodes.
Pick a person and assign them to team A.
For each person they dislike, assign them to team B. If any of those people are already assigned to team A, you've found a conflict, and the answer is no.
For each person on team B, check who they dislike. Assign those people to team A. Again, check for conflicts: If someone disliked by a team B person is already on team B, you've found a conflict, and the answer is no.
Keep going back and forth between the teams, assigning based on dislikes and checking for conflicts. If you reach a person who hasn't been assigned yet, assign them to a team and continue.
If you can assign everyone to a team without a conflict, then the answer is yes, it's possible.

Code Implementation

def possible_bipartition(number_of_people, dislikes):
    graph = [[] for _ in range(number_of_people + 1)]
    for person1, person2 in dislikes:
        graph[person1].append(person2)
        graph[person2].append(person1)

    team_assignments = [0] * (number_of_people + 1)

    def dfs(person, team):
        team_assignments[person] = team

        for disliked_person in graph[person]:
            # Check for conflicting team assignments
            if team_assignments[disliked_person] == team:
                return False

            if team_assignments[disliked_person] == 0:
                # Assign opposite team to disliked person
                if not dfs(disliked_person, -team):
                    return False
        return True

    # Iterate through all people
    for person in range(1, number_of_people + 1):
        # Assign team to unassigned people.
        if team_assignments[person] == 0:
            if not dfs(person, 1):
                return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(N + E) – The algorithm iterates through each person (node), which is represented by N. For each person, it checks their dislikes (edges), represented by E. In the worst-case scenario, the algorithm explores all the edges in the graph to assign people to teams and detect conflicts. The dominant operations are visiting each node and traversing each edge, so the overall time complexity becomes O(N + E), where N is the number of people and E is the number of dislikes.

Space Complexity

O(N) – The algorithm uses a data structure to keep track of which team each person is assigned to. This data structure (implicitly described as 'assigning people to teams') needs to store information for each of the N people, where N is the number of people. Therefore, the auxiliary space required grows linearly with the number of people. This leads to a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty dislike list (no edges)	Return true, as no conflicts exist and bipartition is trivially possible.
Single person (N=1)	Return true, as there are no dislikes and therefore no conflicts.
No possible bipartition (e.g., odd-length cycle in the graph)	The algorithm should return false when a conflict is detected during the coloring process.
Large number of people (N is large)	The solution must be efficient in terms of memory and time complexity to avoid exceeding limits; consider using adjacency list representation for graphs.
Input dislikes list contains duplicate edges	The algorithm should treat duplicate edges as a single edge without affecting the final result.
Disconnected graph (multiple components)	The algorithm needs to iterate through all nodes, handling each disconnected component separately to ensure full coverage.
Complete graph where no bipartition exists	The algorithm should correctly identify the conflict and return false when every pair has a dislike edge between them.
Self-loops in the dislikes (a person dislikes themselves)	The algorithm should either ignore self-loops or immediately return false as they indicate a clear impossibility for bipartition.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the range of values for 'n' and the number of dislikes?
Is an empty dislikes array considered a valid bipartition?
If it's impossible to form a bipartition, what should the function return? (e.g., false, null, throw an exception)?
Can a person dislike themselves? (i.e., can we have entries like [1, 1] in the dislikes array)?
Does the input 'dislikes' guarantee that the person numbers are within the range [1, n], or might they be out of bounds?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by assigning the first person to team A.
Then, try assigning the second person to team A, and then to team B. For each of these options, continue...
For the third person, try assigning them to team A, and then to team B. Again, for each of these options, continue...
Keep doing this for every single person, trying to put them in either team A or team B.
Each time you assign someone to a team, check if they are in the same team as someone they don't get along with. If they are, this team setup doesn't work, so discard it.
If you manage to assign everyone to a team without anyone who dislikes each other ending up on the same team, then you've found a valid way to split the group.
Keep track of whether you find at least one valid way to split the group after exploring all the possibilities. If you do, then it's possible to split the group; otherwise, it's not.

Code Implementation

def possible_bipartition(number_of_people, dislikes):
    team_assignments = [0] * (number_of_people + 1)
    is_bipartite = False

    def backtrack(person_index):
        nonlocal is_bipartite

        # Base case: all people have been assigned to a team
        if person_index == number_of_people + 1:
            is_bipartite = True
            return

        # Try assigning the current person to team 1 or team 2
        for team in [1, 2]:
            team_assignments[person_index] = team

            # Check if the current assignment is valid
            is_valid = True
            for person_one, person_two in dislikes:
                if person_one == person_index:

                    # Ensure disliked people are not on the same team
                    if team_assignments[person_one] == team_assignments[person_two]:
                        is_valid = False
                        break
                elif person_two == person_index:
                    # Ensure disliked people are not on the same team
                    if team_assignments[person_one] == team_assignments[person_two]:
                        is_valid = False
                        break

            # If the current assignment is valid, continue exploring
            if is_valid:
                backtrack(person_index + 1)

            # If a solution is found, stop exploring other branches
            if is_bipartite:
                return

            team_assignments[person_index] = 0

    # Start assigning people to teams from person 1
    backtrack(1)

    # Determine whether there is a valid split
    return is_bipartite

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine each person as a node and each dislike as an edge connecting the nodes.
Pick a person and assign them to team A.
For each person they dislike, assign them to team B. If any of those people are already assigned to team A, you've found a conflict, and the answer is no.
For each person on team B, check who they dislike. Assign those people to team A. Again, check for conflicts: If someone disliked by a team B person is already on team B, you've found a conflict, and the answer is no.
Keep going back and forth between the teams, assigning based on dislikes and checking for conflicts. If you reach a person who hasn't been assigned yet, assign them to a team and continue.
If you can assign everyone to a team without a conflict, then the answer is yes, it's possible.

Code Implementation

def possible_bipartition(number_of_people, dislikes):
    graph = [[] for _ in range(number_of_people + 1)]
    for person1, person2 in dislikes:
        graph[person1].append(person2)
        graph[person2].append(person1)

    team_assignments = [0] * (number_of_people + 1)

    def dfs(person, team):
        team_assignments[person] = team

        for disliked_person in graph[person]:
            # Check for conflicting team assignments
            if team_assignments[disliked_person] == team:
                return False

            if team_assignments[disliked_person] == 0:
                # Assign opposite team to disliked person
                if not dfs(disliked_person, -team):
                    return False
        return True

    # Iterate through all people
    for person in range(1, number_of_people + 1):
        # Assign team to unassigned people.
        if team_assignments[person] == 0:
            if not dfs(person, 1):
                return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty dislike list (no edges)	Return true, as no conflicts exist and bipartition is trivially possible.
Single person (N=1)	Return true, as there are no dislikes and therefore no conflicts.
No possible bipartition (e.g., odd-length cycle in the graph)	The algorithm should return false when a conflict is detected during the coloring process.
Large number of people (N is large)	The solution must be efficient in terms of memory and time complexity to avoid exceeding limits; consider using adjacency list representation for graphs.
Input dislikes list contains duplicate edges	The algorithm should treat duplicate edges as a single edge without affecting the final result.
Disconnected graph (multiple components)	The algorithm needs to iterate through all nodes, handling each disconnected component separately to ensure full coverage.
Complete graph where no bipartition exists	The algorithm should correctly identify the conflict and return false when every pair has a dislike edge between them.
Self-loops in the dislikes (a person dislikes themselves)	The algorithm should either ignore self-loops or immediately return false as they indicate a clear impossibility for bipartition.