Split n People Into Two Groups So No Pair Who Dislike Each Other Shares a Group
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
Input: n = 3, dislikes = []
Output: True
```
With no dislikes, everyone can share one group while the other group stays empty.
Overview: 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.
Read the full ByteDance Software Engineer interview experience this question came from
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.
You are given `n` and a list `dislikes`, where `dislikes[i] = [a, b]` means that person `a` dislikes person `b`. Return `True` (`true` in JavaScript, Java and C++) if everyone can be split into two groups so that no pair in `dislikes` shares a group, and `False` (`false`) otherwise.
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`.
- Every value fits in a signed 32-bit integer; no value can exceed 2^31-1.
Example 1:
Input: n = 4, dislikes = [[1, 2], [2, 3], [3, 4], [1, 4]]
Output: True
Explanation: 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
Explanation: 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.
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.
- Every value fits in a signed 32-bit integer; no value can exceed 2^31-1.
Examples
Input: (1, [])
Expected Output: True
Explanation: Minimum valid input: one person and no dislikes, so that person can go into either group.
Input: (3, [])
Expected Output: True
Explanation: No dislikes among three people: everyone can share one group while the other group stays empty.
Hints
- A pair only says that its two people must end up in different groups; who dislikes whom does not matter, so treat every pair symmetrically.
- Once you choose a group for one person, the group of everyone paired with them is forced, and those choices force others in turn. Ask when such forced choices can contradict each other.
- People who are not linked through any chain of pairs can be placed independently, so every separate cluster of pairs has to be checked, not only the one that contains person 1.