You are given an integer n representing the number of players in a game and a 2D array pick where pick[i] = [xi, yi] represents that the player xi picked a ball of color yi.
Player i wins the game if they pick strictly more than i balls of the same color. In other words,
i wins if they pick at leasti + 1 balls of the same color.Return the number of players who win the game.
Note that multiple players can win the game.
Example 1:
Input: n = 4, pick = [[0,0],[1,0],[1,0],[2,1],[2,1],[2,0]]
Output: 2
Explanation:
Player 0 and player 1 win the game, while players 2 and 3 do not win.
Example 2:
Input: n = 5, pick = [[1,1],[1,2],[1,3],[1,4]]
Output: 0
Explanation:
No player wins the game.
Example 3:
Input: n = 5, pick = [[1,1],[2,4],[2,4],[2,4]]
Output: 1
Explanation:
Player 2 wins the game by picking 3 balls with color 4.
Constraints:
2 <= n <= 101 <= pick.length <= 100pick[i].length == 20 <= xi <= n - 1 0 <= yi <= 10Problem Overview: You are given n players and a list of ball picks where picks[i] = [player, color]. A player i wins if they collect strictly more than i balls of the same color. The task is to count how many players satisfy this winning condition.
Approach 1: Hash Map Approach (O(m) time, O(m) space)
Track how many balls of each color every player collects. Use a hash map keyed by (player, color) and increment the count while iterating through the picks array. Whenever the count for a pair exceeds the player's index player, mark that player as a winner. A set helps ensure each player is counted only once even if multiple colors exceed the threshold.
This approach works well when the number of colors is large or unknown. Hash lookups keep updates constant time, making the entire scan of picks linear. The technique relies on efficient frequency tracking using a hash table and simple counting.
Approach 2: Array Counting Approach (O(m) time, O(n * c) space)
If the number of colors is small or bounded, replace the hash map with a 2D counting array where count[player][color] stores how many balls of that color the player has picked. Iterate through picks, increment the corresponding cell, and check whether the count becomes greater than the player's index. Maintain a boolean array to mark winners so each player contributes to the result once.
This approach avoids hashing overhead and uses direct indexing. It performs well when color IDs are within a predictable range, making array access faster than map operations. The method is essentially a structured version of the same array frequency counting pattern.
Recommended for interviews: The hash map approach is typically expected because it works for any color range without assumptions. The array counting version is a good optimization when constraints guarantee small color values. Showing both demonstrates you understand frequency counting tradeoffs and space optimization.
In this approach, we make use of a two-dimensional hash map. For each pick (where a player picks a ball of a certain color), we increment the count in our hash map. Once all picks are processed, we check each player to determine if they have picked more than the required number of balls of the same color to win.
This solution uses a list of dictionaries, where each dictionary corresponds to a player. The keys of the dictionary are the colors, and the values are the counts of that color picked by the player. We iterate through each player's dictionary and check if any color has been picked more times than required. If so, we increment the count of winning players.
Time Complexity: O(p) where p is the number of entries in the 'pick' list.
Space Complexity: O(n * c) where n is the number of players and c is the number of colors.
This method involves using a simple array structure to count the number of balls each player has picked by color, taking advantage of maximum constraints. This reduces overhead but is less flexible than hash maps.
This solution predefines a fixed-size array to count ball colors for each player based on constraints. This keeps memory usage predictable and direct, by leveraging the small number of players and colors specified in the problem constraints.
Time Complexity: O(p), where p is the number of picks.
Space Complexity: O(n * 10) = O(n), due to known constraints with up to 11 colors and n players.
We can use a 2D array cnt to record the number of balls of each color obtained by each player, and a hash table s to record the IDs of the winning players.
Traverse the pick array, for each element [x, y], we increment cnt[x][y] by one. If cnt[x][y] is greater than x, we add x to the hash table s.
Finally, return the size of the hash table s.
The time complexity is O(m + n times M), and the space complexity is O(n times M). Here, m is the length of the pick array, and n and M are the number of players and the number of colors, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Hash Map Approach | Time Complexity: O(p) where p is the number of entries in the 'pick' list. Space Complexity: O(n * c) where n is the number of players and c is the number of colors. |
| Array Counting Approach | Time Complexity: O(p), where p is the number of picks. Space Complexity: O(n * 10) = O(n), due to known constraints with up to 11 colors and n players. |
| Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Counting | O(m) | O(m) | General case where color range is unknown or large |
| Array Counting | O(m) | O(n * c) | When the color range is small and direct indexing is possible |
Find the Number of Winning Players || Biweekly Contest 136 || Leetcode Solution • codi • 1,303 views views
Watch 6 more video solutions →Practice Find the Number of Winning Players with our built-in code editor and test cases.
Practice on FleetCode