Find Players With Zero or One Losses solution and explanation
Google
9 more videos on this problem
2225. Find Players With Zero or One Losses | 2 Ways to SolveAryan Mittal · 20:09 · 1K views
Leetcode | 2225. Find Players With Zero or One Losses | Medium | Java SolutionDeveloper Docs · 12:02 · 763 views
Leetcode 2225: Find Players With Zero or One LossesAlgorithms Casts · 4:27 · 719 views
Find Players With Zero or One Losses - HashMap - PythonCheatCode Ninja · 3:19 · 527 views
2225. Find Players With Zero or One Losses (Leetcode Medium)Programming Live with Larry · 4:15 · 413 views
Find Players With Zero or One Losses - Google Interview Questions - LeetCode 2225 Solution - C++nexTRIE · 5:53 · 291 views
2225. Find Players With Zero or One Losses | JavaScript | LeetCode Daily Challenge | Detail SolutionLeetCodeWithMonu · 16:17 · 286 views
Leetcode 2225: Find Players With Zero or One Losses | PythonCodeFit · 4:48 · 139 views
Find Players With Zero or One Losses | 2225 Leetcode | Python3CodeMeThere · 9:02 · 129 views
leetcode 2225. Find Players With Zero or One Losses - indegree, outdegreeCode-Yao · 11:00 · 59 views
The problem
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 <= 105matches[i].length == 21 <= winneri, loseri <= 105winneri != 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.
def findWinners(matches):
from collections import defaultdict
losses_count = defaultdict(int)
players = set()
for winner, loser in matches:
players.add(winner)
players.add(loser)
losses_count[loser] += 1
zero_losses = [player for player in players if losses_count[player] == 0]
one_loss = [player for player in players if losses_count[player] == 1]
return [sorted(zero_losses), sorted(one_loss)]import java.util.*;
class Solution {
public List<List<Integer>> findWinners(int[][] matches) {
Map<Integer, Integer> countMap = new HashMap<>();
Set<Integer> allPlayers = new HashSet<>();
for (int[] match : matches) {
allPlayers.add(match[0]);
allPlayers.add(match[1]);
countMap.put(match[1], countMap.getOrDefault(match[1], 0) + 1);
}
List<Integer> noLosses = new ArrayList<>();
List<Integer> oneLoss = new ArrayList<>();
for (int player : allPlayers) {
int loss = countMap.getOrDefault(player, 0);
if (loss == 0) {
noLosses.add(player);
} else if (loss == 1) {
oneLoss.add(player);
}
}
Collections.sort(noLosses);
Collections.sort(oneLoss);
List<List<Integer>> answer = new ArrayList<>();
answer.add(noLosses);
answer.add(oneLoss);
return answer;
}
}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.
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.
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> findWinners(vector<vector<int>>& matches) {
vector<int> losses(100001, 0), played(100001, 0);
for (auto& match : matches) {
played[match[0]] = 1;
played[match[1]] = 1;
losses[match[1]]++;
}
vector<int> noLosses, oneLoss;
for (int i = 1; i <= 100000; ++i) {
if (played[i]) {
if (losses[i] == 0) noLosses.push_back(i);
else if (losses[i] == 1) oneLoss.push_back(i);
}
}
return {noLosses, oneLoss};
}function findWinners(matches) {
const losses = new Array(100001).fill(0), played = new Array(100001).fill(false);
matches.forEach(([winner, loser]) => {
played[winner] = true;
played[loser] = true;
losses[loser]++;
});
const noLosses = [], oneLoss = [];
for (let i = 1; i <= 100000; i++) {
if (played[i]) {
if (losses[i] === 0) noLosses.push(i);
else if (losses[i] === 1) oneLoss.push(i);
}
}
return [noLosses, oneLoss];
}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.
Time Complexity: O(n log n)
Space Complexity: O(n)
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.
function findWinners(matches: number[][]): number[][] {
const cnt: Map<number, number> = new Map();
for (const [winner, loser] of matches) {
if (!cnt.has(winner)) {
cnt.set(winner, 0);
}
cnt.set(loser, (cnt.get(loser) || 0) + 1);
}
const ans: number[][] = [[], []];
for (const [x, v] of cnt) {
if (v < 2) {
ans[v].push(x);
}
}
ans[0].sort((a, b) => a - b);
ans[1].sort((a, b) => a - b);
return ans;
}func findWinners(matches [][]int) [][]int {
cnt := map[int]int{}
for _, e := range matches {
if _, ok := cnt[e[0]]; !ok {
cnt[e[0]] = 0
}
cnt[e[1]]++
}
ans := make([][]int, 2)
for x, v := range cnt {
if v < 2 {
ans[v] = append(ans[v], x)
}
}
sort.Ints(ans[0])
sort.Ints(ans[1])
return ans
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
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.