#2225

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find Players With Zero or One Losses

Identify players with zero or one losses by efficiently scanning arrays and counting losses using hash lookups for accuracy.

array hash table sorting counting

Problem Statement

Given an integer array matches where each element matches[i] = [winneri, loseri] indicates that player winneri defeated player loseri, identify players based on their loss counts.

Return a list of two lists: the first contains players who have zero losses, and the second contains players who have exactly one loss. Both lists must be sorted in increasing order.

Examples

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]]

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. Thus, answer[0] = [1,2,10] and answer[1] = [4,5,7,8].

Example 2

Input: matches = [[2,3],[1,3],[5,4],[6,4]]

Output: [[1,2,5,6],[]]

Players 1, 2, 5, and 6 have not lost any matches. Players 3 and 4 each have lost two matches. Thus, answer[0] = [1,2,5,6] and answer[1] = [].

Constraints

1 <= matches.length <= 105
matches[i].length == 2
1 <= winneri, loseri <= 105
winneri != loseri
All matches[i] are unique.

Solution Approach

Hash map to count losses

Iterate through matches and update a hash map where keys are player IDs and values are the number of losses. This allows O(1) updates per match and avoids missing players who never lose.

Separate players by loss count

After counting, scan the hash map to collect players with zero losses and exactly one loss into two separate lists. This isolates the two target categories efficiently without multiple passes over the original array.

Sort the results

Sort both lists before returning to satisfy the requirement of increasing order. Sorting ensures the output is consistent and prevents errors from relying on hash map insertion order.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + k log k) where n is the number of matches and k is the number of unique players, due to array scanning and sorting. Space complexity is O(k) for the hash map storing loss counts.

What Interviewers Usually Probe

Expect discussion on hash table versus array-only counting trade-offs.
Watch for missed edge cases like players with no matches.
Check if candidates sort results before returning to meet output order requirements.

Common Pitfalls or Variants

Common pitfalls

Failing to include players who never lost any match in the zero-loss list.
Incorrectly counting multiple losses for a player when matches list contains repeated winners or losers.
Returning unsorted lists which violates the increasing order requirement.

Follow-up variants

Find players with exactly k losses instead of zero or one.
Return players grouped by total wins instead of losses.
Handle cases with duplicate matches or missing players in the dataset.

FAQ

What is the main pattern used in Find Players With Zero or One Losses?

The main pattern is array scanning combined with a hash lookup to count losses efficiently.

How do I handle players who never lost any match?

Track all players in the hash map and assign zero losses by default for players not appearing as losers.

Do the output lists need to be sorted?

Yes, both lists must be returned in increasing order to match problem requirements.

Can this problem handle large numbers of matches?

Yes, using a hash map for loss counts ensures linear time scanning with reasonable space usage.

What common mistakes should I avoid?

Avoid missing zero-loss players, double-counting losses, and returning unsorted lists.

terminal

Solution

Solution 1: Hash Table + Sorting

We use a hash table `cnt` to record the number of matches each player has lost.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
        cnt = Counter()
        for winner, loser in matches:
            if winner not in cnt:
                cnt[winner] = 0
            cnt[loser] += 1
        ans = [[], []]
        for x, v in sorted(cnt.items()):
            if v < 2:
                ans[v].append(x)
        return ans

Continue Practicing

#2248 intersection of multiple arrays #1782 count pairs of nodes #1481 least number of unique integers after k removals