Find Players With Zero or One Losses
01 · Problem
You are given the results of a tournament as an array matches, where matches[i] = [winner_i, loser_i] records that player winner_i beat player loser_i.
Return a list answer of length 2:
answer[0]contains every player who never lost a match.answer[1]contains every player who lost exactly one match.
Only players who appear in at least one match are considered. Both lists must be sorted in increasing order, and a list with no players is returned as [].
02 · Examples
matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
[[1,2,10],[4,5,7,8]]
Players 1, 2 and 10 never lost. Players 4, 5, 7 and 8 lost once each. Players 3, 6 and 9 lost twice.
matches = [[2,3],[1,3],[5,4],[6,4]]
[[1,2,5,6],[]]
Players 1, 2, 5 and 6 never lost. Players 3 and 4 each lost twice, so the second list is empty.
matches = [[1,2]]
[[1],[2]]
Player 1 has no losses and player 2 has exactly one.
03 · Constraints
- 011 <= matches.length <= 105
- 02matches[i].length == 2
- 031 <= winner_i, loser_i <= 105
- 04winner_i != loser_i
- 05No pair [winner_i, loser_i] appears more than once
04 · Optimal complexity
- Time
- O(m + p log p)
- Space
- O(p)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.