Welcome to Subscribe On Youtube
3238. Find the Number of Winning Players
Description
You are given an integer n
representing the number of players in a game and a 2D array pick
where pick[i] = [x_{i}, y_{i}]
represents that the player x_{i}
picked a ball of color y_{i}
.
Player i
wins the game if they pick strictly more than i
balls of the same color. In other words,
 Player 0 wins if they pick any ball.
 Player 1 wins if they pick at least two balls of the same color.
 ...
 Player
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 <= 10
1 <= pick.length <= 100
pick[i].length == 2
0 <= x_{i} <= n  1
0 <= y_{i} <= 10
Solutions
Solution 1: Counting
We can use a 2D array $\textit{cnt}$ to record the number of balls of each color obtained by each player, and a hash table $\textit{s}$ to record the IDs of the winning players.
Traverse the $\textit{pick}$ array, for each element $[x, y]$, we increment $\textit{cnt}[x][y]$ by one. If $\textit{cnt}[x][y]$ is greater than $x$, we add $x$ to the hash table $\textit{s}$.
Finally, return the size of the hash table $\textit{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 $\textit{pick}$ array, and $n$ and $M$ are the number of players and the number of colors, respectively.

class Solution { public int winningPlayerCount(int n, int[][] pick) { int[][] cnt = new int[n][11]; Set<Integer> s = new HashSet<>(); for (var p : pick) { int x = p[0], y = p[1]; if (++cnt[x][y] > x) { s.add(x); } } return s.size(); } }

class Solution { public: int winningPlayerCount(int n, vector<vector<int>>& pick) { int cnt[10][11]{}; unordered_set<int> s; for (const auto& p : pick) { int x = p[0], y = p[1]; if (++cnt[x][y] > x) { s.insert(x); } } return s.size(); } };

class Solution: def winningPlayerCount(self, n: int, pick: List[List[int]]) > int: cnt = [[0] * 11 for _ in range(n)] s = set() for x, y in pick: cnt[x][y] += 1 if cnt[x][y] > x: s.add(x) return len(s)

func winningPlayerCount(n int, pick [][]int) int { cnt := make([][11]int, n) s := map[int]struct{}{} for _, p := range pick { x, y := p[0], p[1] cnt[x][y]++ if cnt[x][y] > x { s[x] = struct{}{} } } return len(s) }

function winningPlayerCount(n: number, pick: number[][]): number { const cnt: number[][] = Array.from({ length: n }, () => Array(11).fill(0)); const s = new Set<number>(); for (const [x, y] of pick) { if (++cnt[x][y] > x) { s.add(x); } } return s.size; }