README_EN.md

comments	difficulty	edit_url	rating	source	tags
true	Easy	https://github.com/doocs/leetcode/edit/main/solution/3200-3299/3238.Find%20the%20Number%20of%20Winning%20Players/README_EN.md	1285	Biweekly Contest 136 Q1	Array Hash Table Counting

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.

Python3

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)

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

C++

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

Go

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)
}

TypeScript

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;
}