FastPrep
Problem · Graph

Possible Bipartition

Learn this problem
● MediumCoupang logoCoupangFULLTIMEPHONE SCREEN

Problem statement

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

Return true if all people can be split into two groups satisfying every pair, otherwise return false.

Function

possibleBipartition(n: int, dislikes: int[][]) → boolean

Examples

Example 1

n = 4dislikes = [[1,2],[1,3],[2,4]]return = true

One valid split is {1,4} and {2,3}.

Example 2

n = 3dislikes = [[1,2],[1,3],[2,3]]return = false

The three people form an odd cycle, so two groups are impossible.

Constraints

  • 1 <= n <= 2000.
  • 0 <= dislikes.length <= 10000.
  • 1 <= a, b <= n and a != b.
  • No dislike pair is duplicated.
drafts saved locally
public boolean possibleBipartition(int n, int[][] dislikes) {
    // Write your code here.
}
n4
dislikes[[1,2],[1,3],[2,4]]
expectedtrue
checking account