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:
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. 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],[]] Explanation: 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 <= 105matches[i].length == 21 <= winneri, loseri <= 105winneri != loserimatches[i] are unique.Problem Overview: You receive a list of match results where matches[i] = [winner, loser]. Each pair represents one game. The goal is to return two sorted lists: players who never lost and players who lost exactly once.
Approach 1: Using Hash Maps to Track Wins and Losses (O(n log n) time, O(n) space)
Use a hash map to count how many times each player loses. Iterate through the match list once. For every match, ensure the winner exists in the map with zero losses if they have not been seen before, then increment the loss count for the loser. After processing all matches, iterate over the map to separate players with 0 losses and 1 loss. Finally, sort both result lists. The hash lookup keeps updates O(1) on average, while sorting the final player lists gives an overall time complexity of O(n log n).
This approach works well for the general case because player IDs can be large and sparse. Hash maps dynamically store only the players that appear in matches. It directly models the problem as a counting task using a hash table and simple iteration over an array.
Approach 2: Using Two Separate Arrays for Winners and Losers (O(n log n) time, O(n) space)
Instead of a hash map, maintain a loss counter array indexed by player ID. First determine the maximum player number from the matches to size the array. Then iterate through the matches and increment the loss count for each loser. Winners are tracked implicitly because they appear in the match list even if they never lose. After counting, scan the array: players with 0 losses go into the "never lost" list (if they appeared in matches), and players with exactly 1 loss go into the second list. Sort both lists before returning.
This approach replaces hash lookups with direct indexing, which can be slightly faster when player IDs are small and bounded. It turns the problem into a simple counting exercise followed by sorting of the results.
Recommended for interviews: The hash map counting approach is usually expected. It handles arbitrary player IDs and shows you understand frequency counting with constant‑time lookups. Starting with a brute-force idea (tracking all matches per player) demonstrates reasoning, but the optimized hash map solution shows practical problem‑solving skills.
This approach involves using hash maps (or dictionaries) to track the number of matches each player has won and lost. We loop over the matches to populate these maps. Finally, we iterate over the accumulated data to build the two result lists: players with zero losses and players with exactly one loss. We then sort these lists before returning them.
We use a dictionary to count the number of losses for each player. We also maintain a set of all players to ensure that we consider only those who have played matches. By checking the dictionary, we categorize players into those with zero and one loss, sort them, and return the result.
Time Complexity: O(n log n) due to the sorting of players.
Space Complexity: O(n) for storing player and loss information.
In this approach, we maintain two numerical arrays or lists: one to track whether a player has won, and another to count how many times a player has lost. We then deduce the needed lists by examining these arrays.
Using two arrays of size 100,001 ensures constant time access for any player index. The 'losses' array stores the count of losses for each player, and the 'played' array indicates whether a player has participated. Finally, we evaluate these arrays to find and sort players with zero or one loss.
C++
JavaScript
Time Complexity: O(n log n)
Space Complexity: O(n)
We use a hash table cnt to record the number of matches each player has lost.
Then we traverse the hash table, put the players who lost 0 matches into ans[0], and put the players who lost 1 match into ans[1].
Finally, we sort ans[0] and ans[1] in ascending order and return the result.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the number of matches.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Using Hash Maps to Track Wins and Losses | Time Complexity: O(n log n) due to the sorting of players. |
| Using Two Separate Arrays for Winners and Losers | Time Complexity: O(n log n) |
| Hash Table + Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map to Track Loss Counts | O(n log n) | O(n) | General case where player IDs may be large or sparse |
| Counting Array for Loss Tracking | O(n log n) | O(n) | When player IDs are bounded and direct indexing is efficient |
Find Players With Zero or One Losses | Google | Leetcode 2225 • codestorywithMIK • 31,415 views views
Watch 9 more video solutions →Practice Find Players With Zero or One Losses with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor