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.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.
Java
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.
JavaScript
Time Complexity: O(n log n)
Space Complexity: O(n)
| 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) |
2225. Find Players With Zero or One Losses - Day 28/30 Leetcode November Challenge • Programming Live with Larry • 987 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