Problem Statement in English

You’re given n people numbered from 1 to n. You are also given an array dislikes where dislikes[i] = [a, b] indicates that the person numbered a does not like the person numbered b.

You want to split everyone into two groups of any size such that no person in one group dislikes a person in the other group.

Return true if it is possible to split everyone into two groups in this way, or false otherwise.

Approach

The idea is that we don’t even need to find the 2 final groups. We just need to check if we can make as many groups as possible which are mutually exclusive. If these are stable, then we can return True. If not, then we return False.

First we need to create an adjacency list from the dislikes array. This will help us to easily find the neighbors of each person. Each pair of people who dislike each other will be connected in the graph.

Then we can use a union-find data structure. We can iterate through the neighbors of each person and for each pair of people, we can check if they belong to the same group. If they do, then we return False. If they don’t, then we can union them together.

This may result in multiple connected components in the graph, but that’s fine. As long as each component is stable, we can return True. If it fails for any component, we can return False.

And we’re done!

Solution in Python


class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        parent = [i for i in range(n)]

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(a, b):
            pa, pb = find(a), find(b)
            parent[b] = pa

        adj = defaultdict(list)

        for a, b in dislikes:
            adj[a - 1].append(b - 1)
            adj[b - 1].append(a - 1)

        for i in range(n):
            nei = adj[i]
            this = find(i)

            if not nei: continue

            for j in nei[1:]:
                if this == find(j):
                    return False
                union(nei[0], j)

        return True

Complexity

  • Time: $O(n + m)$
    Where n is the number of people and m is the number of dislikes. Since we iterate through all the people and all the dislikes.

  • Space: $O(n)$
    Since we store the parent array and the adjacency list.

Mistakes I Made

I had to look this up :(

And we are done.