FastPrepConstruct a Possible Bipartition

Construct a Possible Bipartition

Airbnb logoAirbnb● MediumFULLTIMEOA
Learn

Problem statement

There are n people numbered from 1 through n. Each pair [a, b] in dislikes means that people a and b must be placed in different groups.

Construct two groups that contain every person exactly once and satisfy every dislike pair. Process people in increasing order. Whenever the next person is still unassigned, place that person in group 1 and color the entire connected component consistently. Sort both completed groups in increasing order.

If a valid partition exists, return group1|group2, where each group is its comma-separated list of person IDs. An empty group is represented by an empty string. If no valid partition exists, return IMPOSSIBLE.

Function

bipartitionGroups(n: int, dislikes: int[][]) → String

Examples

Example 1

n = 4dislikes = [[1,2],[1,3],[2,4]]return = "1,4|2,3"

Starting from person 1 puts people 2 and 3 in the opposite group. Person 4 must then share group 1 with person 1.

Example 2

n = 3dislikes = [[1,2],[2,3],[1,3]]return = "IMPOSSIBLE"

The three edges form an odd cycle, so two colors cannot satisfy every dislike pair.

Example 3

n = 5dislikes = [[1,2],[3,4]]return = "1,3,5|2,4"

People 1, 3, and isolated person 5 seed their components in group 1; their constrained neighbors go to group 2.

Constraints

  • 1 <= n <= 2000.
  • 0 <= dislikes.length <= 10000.
  • Every pair contains two distinct values in [1, n].
  • No dislike pair is repeated.

More Airbnb problems

See Airbnb hiring insights
public String bipartitionGroups(int n, int[][] dislikes) {
    // Write your code here.
}
n4
dislikes[[1,2],[1,3],[2,4]]
expected"1,4|2,3"
Checking account…