# Find the Number of Winning Players
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-number-of-winning-players)
Canonical: https://scaleengineer.com/dsa/problems/find-the-number-of-winning-players
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
---
## Problem
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 least `i + 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`

# Approaches
## Brute-Force Iteration
This approach directly translates the problem statement into code. It iterates through each player and, for each player, iterates through all possible colors. For each player-color combination, it scans the entire `pick` array to count how many balls of that color the player has picked. If this count exceeds the player's index, the player is marked as a winner.
**Time:** O(n * C * L), where `n` is the number of players, `C` is the number of possible colors (11 in this case), and `L` is the length of the `pick` array. The three nested loops dominate the runtime. · **Space:** O(n) to store the `hasWon` boolean array.
**Pros:** Simple to understand and implement directly from the problem definition.
**Cons:** Highly inefficient due to repeated scanning of the `pick` array.; For larger inputs, this would be too slow.
### Explanation
This method involves a straightforward, yet inefficient, triple-nested loop structure.
The logic is as follows:
1.  We iterate through every player from `0` to `n-1`.
2.  For each player, we iterate through every possible color.
3.  For each player-color pair, we perform a full scan of the `pick` array to count the occurrences.
4.  If this count is greater than the player's index `p`, we've found a winning condition.
5.  A boolean array `hasWon` is used to ensure we only count each winning player once, even if they meet the winning criteria with multiple colors.

Here is the Java implementation:
```java
class Solution {
    public int numberOfWinners(int n, int[][] pick) {
        int winners = 0;
        boolean[] hasWon = new boolean[n];

        // Iterate through each player
        for (int p = 0; p < n; p++) {
            // Iterate through each possible color
            for (int c = 0; c <= 10; c++) { // Max color is 10
                int count = 0;
                // Scan the entire pick array to count
                for (int[] currentPick : pick) {
                    if (currentPick[0] == p && currentPick[1] == c) {
                        count++;
                    }
                }

                // Check winning condition
                if (count > p) {
                    if (!hasWon[p]) {
                        winners++;
                        hasWon[p] = true;
                    }
                }
            }
        }
        return winners;
    }
}
```
### Algorithm
*   Initialize a counter for winning players, `winners`, to 0.
*   Create a boolean array, `hasWon`, of size `n` to track which players have already been counted as winners.
*   Loop through each player `p` from `0` to `n-1`.
*   Inside this loop, loop through each possible color `c` (from 0 to 10, based on constraints).
*   For each `(p, c)` pair, initialize a `count` to 0.
*   Iterate through the `pick` array. If an entry `[player, color]` matches `(p, c)`, increment `count`.
*   After counting, check if `count > p`.
*   If the condition is true and `hasWon[p]` is false, it means player `p` is a winner. Increment `winners` and set `hasWon[p]` to true.
*   After all loops complete, return `winners`.

## Optimized Counting using a 2D Array
This approach improves upon the brute-force method by pre-processing the `pick` array to efficiently count the balls for each player. It uses a 2D array to store the counts of each color for each player. This avoids re-scanning the `pick` array repeatedly. After counting, it iterates through the players to check the winning condition against the stored counts.
**Time:** O(L + n * C), where `L` is the length of the `pick` array, `n` is the number of players, and `C` is the number of possible colors (11). We iterate through `pick` once (`O(L)`) and then check the counts for each player and color (`O(n * C)`). · **Space:** O(n * C) to store the `counts` in the 2D array, where C is the number of colors.
**Pros:** Significantly more efficient than the brute-force approach.; Processes the input `pick` array only once.
**Cons:** Requires extra space for the counts data structure, but this is minimal given the problem constraints.
### Explanation
This optimized approach avoids redundant computations by first aggregating all the pick data into a more suitable data structure. A 2D array is a perfect choice given the small and fixed ranges for player IDs and colors.

The process is divided into two main phases:
1.  **Counting Phase:** We iterate through the `pick` array just once. For each pick `[player, color]`, we increment a counter in our 2D array `counts[player][color]`. This phase populates our `counts` array in linear time with respect to the number of picks.
2.  **Checking Phase:** After all counts are gathered, we iterate through each player `p`. For each player, we check their counts for all possible colors. If we find any color `c` where `counts[p][c]` is greater than `p`, we know the player has won. We increment our winner count and immediately `break` from the inner loop to check the next player, preventing double counting.

Here is the Java implementation:
```java
class Solution {
    public int numberOfWinners(int n, int[][] pick) {
        // counts[player][color] stores the number of balls of that color picked by the player.
        // Constraints: n <= 10, color <= 10.
        int[][] counts = new int[n][11];

        // 1. Counting Phase
        for (int[] p : pick) {
            int player = p[0];
            int color = p[1];
            counts[player][color]++;
        }

        int winners = 0;
        // 2. Checking Phase
        for (int p = 0; p < n; p++) {
            for (int c = 0; c <= 10; c++) {
                // Winning condition: picked strictly more than p balls of the same color.
                if (counts[p][c] > p) {
                    winners++;
                    break; // Player p has won, move to the next player.
                }
            }
        }
        return winners;
    }
}
```
### Algorithm
*   Create a 2D array, `counts`, of size `n x 11` (for `n` players and 11 possible colors 0-10), initialized to zeros. This will store `counts[player][color]`.
*   Iterate through the `pick` array once. For each entry `[player, color]`, increment `counts[player][color]`.
*   Initialize a counter for winning players, `winners`, to 0.
*   Loop through each player `p` from `0` to `n-1`.
*   For each player `p`, loop through each color `c` from `0` to `10`.
*   Check if `counts[p][c] > p`.
*   If the condition is true, player `p` is a winner. Increment `winners` and `break` the inner color loop to proceed to the next player (as we only count each player once).
*   After the loops complete, return `winners`.

# Solutions
### Java

```java
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();
  }
}

```

### CPP

```cpp
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();
  }
};

```

### Python

```python
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)

```