# 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] = [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,

• 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 <= xi <= n - 1
• 0 <= yi <= 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) {
}
}
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:
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) {