Skip to content

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.

1
2
3
4
5
6
7
8
9
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
}

Comments