Skip to main content
Talentd

Find Players With Zero or One Losses - Solution & Explanation

MediumArrayHash TableSortingCounting10 min readAsked at: Palantir, Google, Indeed +1
Practice this problem

Problem Statement

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.
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 <= 105
  • matches[i].length == 2
  • 1 <= winneri, loseri <= 105
  • winneri != loseri
  • All matches[i] are unique.

Approach Overview

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.

Approach 1: Using Hash Maps to Track Wins and Losses

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.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n log n) due to the sorting of players.
Space Complexity: O(n) for storing player and loss information.

Try this approach in the editor →

Approach 2: Using Two Separate Arrays for Winners and Losers

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.

Code

C++JavaScript

C++

JavaScript

Complexity

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

Try this approach in the editor →

Approach 3: Hash Table + Sorting

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.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Hash Maps to Track Wins and Losses

Time Complexity: O(n log n) due to the sorting of players.
Space Complexity: O(n) for storing player and loss information.

Using Two Separate Arrays for Winners and Losers

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

Hash Table + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map to Track Loss CountsO(n log n)O(n)General case where player IDs may be large or sparse
Counting Array for Loss TrackingO(n log n)O(n)When player IDs are bounded and direct indexing is efficient

Video Solution

2225. Find Players With Zero or One Losses | 2 Ways to Solve • Aryan Mittal • 1,289 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Players With Zero or One Losses easy or hard?
LeetCode classifies this problem as Medium, but many developers find it closer to an easy counting problem once the pattern is recognized. The challenge is mainly identifying that you only need to track the number of losses per player and then categorize them.
Find Players With Zero or One Losses Python/Java solution
In Python and Java, the typical solution uses a dictionary or HashMap to count losses for each player while iterating through the matches array. After building the map, iterate through it to separate players with 0 and 1 loss, then sort both lists before returning them.
How to solve Find Players With Zero or One Losses in O(n)?
Loss counting itself is O(n) by iterating through the matches once and updating a hash map or counting array. However, the problem requires sorted output, which usually adds O(n log n) sorting time. If the player IDs are bounded and you iterate in numeric order using a counting array, you can effectively achieve near O(n) total time.
What is the best approach for Find Players With Zero or One Losses?
The most common approach uses a hash map to count how many times each player loses. Iterate through all matches, update the loss count for the loser, and ensure winners exist in the map with zero losses. After processing, collect players with 0 losses and exactly 1 loss, then sort them. This runs in O(n log n) time due to sorting and uses O(n) space.
Is Find Players With Zero or One Losses asked at Google/Amazon/Meta?
Problems involving frequency counting with hash maps appear frequently in interviews at companies like Amazon, Google, and Meta. This problem specifically tests your ability to aggregate results from pairwise events and categorize entities based on counts, which is a common interview pattern.
What data structure is used in Find Players With Zero or One Losses?
The core data structure is a hash table (hash map) that tracks how many losses each player has. Some implementations also use arrays for counting when player IDs are small enough. The final result lists are sorted using standard sorting algorithms.
What is the time complexity of Find Players With Zero or One Losses?
The typical solution runs in O(n log n) time where n is the number of matches. Counting losses with a hash map takes O(n), and sorting the resulting player lists takes O(k log k). Space complexity is O(n) because the algorithm stores loss counts for each unique player.

Ready to solve this problem?

Practice Find Players With Zero or One Losses with our built-in code editor and test cases.

Practice on FleetCode
Previous

Lowest Common Ancestor of a Binary Tree