Katkat
Back

Split n People Into Two Groups So No Pair Who Dislike Each Other Shares a Group

ByteDanceSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Given n people and a list of pairs who dislike each other, decide whether everyone can be divided into two groups of any size so that no disliking pair shares a group. The problem tests reasoning about pairwise constraints, people with no constraints, and a solution that runs in time linear in the number of people and pairs.

There are n people, labeled from 1 to n, and you want to split them into two groups of any size. Some people dislike others, and a person must not end up in the same group as anyone they dislike. Given n and the list dislikes, where dislikes[i] = [a, b] means that person a dislikes person b, return True if everyone can be split into two groups so that no pair in dislikes shares a group, and False otherwise.

Function Signature

def can_split_into_two_groups(n: int, dislikes: list[list[int]]) -> bool:

Rules

  • Every person from 1 to n goes into exactly one of the two groups.
  • Either group may have any size, including zero.
  • A pair [a, b] forbids a and b from sharing a group; which of the two dislikes the other does not change the requirement.
  • A person who appears in no pair may go into either group.
  • Return True if at least one valid split exists, and False otherwise.

Constraints

  • 1 <= n <= 2000
  • 0 <= len(dislikes) <= 10^4
  • len(dislikes[i]) == 2
  • 1 <= dislikes[i][0] < dislikes[i][1] <= n
  • No pair appears more than once in dislikes.

Examples

Example 1

Input: n = 4, dislikes = [[1, 2], [2, 3], [3, 4], [1, 4]]
Output: True

The groups {1, 3} and {2, 4} separate every pair.

Example 2

Input: n = 6, dislikes = [[1, 2], [3, 4], [4, 5], [3, 5]]
Output: False

People 3, 4 and 5 each dislike the other two, and two groups cannot keep three people pairwise apart, wherever people 1, 2 and 6 go.

Example 3

Input: n = 3, dislikes = []
Output: True

With no dislikes, everyone can share one group while the other group stays empty.