FunctionRacerProblemsRace

Smallest Team Split

MediumGraphsPython, JavaScript, TypeScript, Java, C++

rivals[i] lists the players that player i refuses to share a team with. Players are numbered 0 to len(rivals) - 1. The lists are symmetric: if j is in rivals[i] then i is in rivals[j]. Nobody is their own rival, and a list may repeat a player.

Split the players into team 1 and team 2 so that no two rivals are on the same team, and return a list team where team[i] is 1 or 2. If several splits work, return the lexicographically smallest list: at the first index where two valid lists differ, pick the one holding 1. Return the empty list [] if no split is possible.

Example 1

rivals [[1],[0,2],[1]]
returns [1,2,1]

Player 1 must be apart from both 0 and 2. Giving player 0 team 1 forces [1, 2, 1], the smallest valid list.

Example 2

rivals [[1,2],[0,2],[0,1]]
returns []

Three players who all refuse each other cannot fit into two teams.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems