Find Players With Zero or One Losses
MedPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a HashMap to store the number of losses for each player. We first iterate through all the matches to populate this map. It's important to also add players who only win to the map, so we can identify them later. After counting all losses, we iterate through the map's entries to categorize players into those with zero or one loss. Finally, since the output requires sorted lists, we sort these two lists before returning the result.
Algorithm
- Initialize a
HashMap<Integer, Integer>calledlossesCountto store the loss count for each player. - Iterate through the
matchesarray. For each match[winner, loser]:- Ensure the
winneris in the map. If they are not present, add them with a loss count of 0. This is crucial for players who never lose. - Increment the loss count for the
loser. If they are not in the map, add them with a count of 1.
- Ensure the
- Initialize two lists,
zeroLossesandoneLoss. - Iterate through the entries of the
lossesCountmap.- If a player's loss count is 0, add them to the
zeroLosseslist. - If a player's loss count is 1, add them to the
oneLosslist.
- If a player's loss count is 0, add them to the
- Sort both
zeroLossesandoneLosslists in ascending order usingCollections.sort(). - Return a list containing the sorted
zeroLossesandoneLosslists.
Walkthrough
In this method, we use a HashMap to keep track of the number of losses for every player who has participated in at least one match. We iterate through the matches array once. For each match, we update the loss count for the loser. A key detail is to also account for players who have only won. We can do this by ensuring every winner is also present in our map, with a loss count of 0 if they haven't lost yet. After processing all matches, the map contains all players and their total losses. We then create two separate lists, one for players with zero losses and one for players with one loss, by iterating through our map. The final step is to sort these two lists as required by the problem statement.
import java.util.*; class Solution { public List<List<Integer>> findWinners(int[][] matches) { Map<Integer, Integer> lossesCount = new HashMap<>(); for (int[] match : matches) { int winner = match[0]; int loser = match[1]; lossesCount.put(winner, lossesCount.getOrDefault(winner, 0)); lossesCount.put(loser, lossesCount.getOrDefault(loser, 0) + 1); } List<Integer> zeroLosses = new ArrayList<>(); List<Integer> oneLoss = new ArrayList<>(); for (Map.Entry<Integer, Integer> entry : lossesCount.entrySet()) { int player = entry.getKey(); int losses = entry.getValue(); if (losses == 0) { zeroLosses.add(player); } else if (losses == 1) { oneLoss.add(player); } } Collections.sort(zeroLosses); Collections.sort(oneLoss); return Arrays.asList(zeroLosses, oneLoss); }}Complexity
Time
O(M + P log P), where M is the number of matches and P is the number of unique players. It takes O(M) to populate the HashMap. Then, it takes O(P) to iterate through the map and O(P log P) to sort the result lists. The sorting step dominates the complexity.
Space
O(P), where P is the number of unique players. This space is used to store the `lossesCount` map and the final result lists.
Trade-offs
Pros
Conceptually straightforward and easy to implement.
Flexible and works well even if player IDs are very large or not within a contiguous range, as it doesn't depend on the magnitude of the IDs.
Cons
The final sorting step (O(P log P)) makes it less efficient than approaches that can build the sorted lists directly, especially given the problem's constraints on player IDs.
HashMaps have a higher constant factor overhead compared to direct array access.
Solutions
Solution
class Solution {public List<List<Integer>> findWinners(int[][] matches) { Map<Integer, Integer> cnt = new HashMap<>(); for (int[] m : matches) { int a = m[0], b = m[1]; cnt.putIfAbsent(a, 0); cnt.put(b, cnt.getOrDefault(b, 0) + 1); } List<List<Integer>> ans = new ArrayList<>(); ans.add(new ArrayList<>()); ans.add(new ArrayList<>()); for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) { int u = entry.getKey(); int v = entry.getValue(); if (v < 2) { ans.get(v).add(u); } } Collections.sort(ans.get(0)); Collections.sort(ans.get(1)); return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.