Find Players With Zero or One Losses

medium LeetCode #2225
array hash-table sorting counting

Description

You are given an integer array matches where matches[i] = [winneri, loseri] indicates that the player winneri defeated player loseri in a match.

Return a list answer of size 2 where:
- answer[0] is a list of all players that have not lost any matches.
- answer[1] is a list of all players that have lost exactly one match.

The values in the two lists should be returned in increasing order.

Note: You should only consider the players that have played at least one match. The testcases will be generated such that no two matches will have the same outcome.

Example 1:
Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
Output: [[1,2,10],[4,5,7,8]]
Explanation:
Players 1, 2, and 10 have not lost any matches.
Players 4, 5, 7, and 8 each have lost one match.
Players 3, 6, and 9 each have lost two matches, so they are not included.

Example 2:
Input: matches = [[2,3],[1,3],[5,4],[6,4]]
Output: [[1,2,5,6],[]]
Explanation:
Players 1, 2, 5, and 6 have not lost any matches.
Players 3 and 4 each have lost two matches, so no one has exactly one loss.

Example 3:
Input: matches = [[1,2]]
Output: [[1],[2]]
Explanation:
Player 1 has zero losses (won against 2).
Player 2 has exactly one loss (lost to 1).

Constraints

  • 1 <= matches.length <= 10^5
  • matches[i].length == 2
  • 1 <= winneri, loseri <= 10^5
  • winneri != loseri
  • All matches[i] are unique

Complexity

Show Complexity
  • Time: O(n log n)
  • Space: O(n)

Hints

Show Hints
Pattern
Hash map counting
Approach
Use a map to count losses. Winners with 0 losses go to answer[0], players with exactly 1 loss go to answer[1]
Complexity
Track loss count per player, then filter and sort

Solutions

Show PY Solution 
from collections import defaultdict


def solution(matches: list[list[int]]) -> list[list[int]]:
    lm = defaultdict(int)

    for w, l in matches:
        lm[w] += 0
        lm[l] += 1

    winners = []
    losers = []
    for k, v in lm.items():
        if v == 1:
            losers.append(k)
        elif v == 0:
            winners.append(k)

    winners = sorted(winners)
    losers = sorted(losers)

    return [winners, losers]