3238. Find the Number of Winning Players

EasyArrayHash TableCounting

Problem 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 least i + 1 balls of the same color.

Your task is to return the number of players who win the game. Note that multiple players can win the game.

Intuition

The solution involves recording how many balls of each color each player has picked. We use a 2D array cnt where cnt[x][y] records the number of balls of color y picked by player x. As we go through each ball picked by each player in the pick array, we update our cnt array.

For any player x, if the count of balls of a particular color exceeds x, then this player has won the game. To track this, we use a set s to store the IDs of such winning players, as sets automatically handle duplicates and help in ensuring we only track each player once.

In conclusion, after processing all the picks, the problem reduces to simply returning the size of set s, which tells us how many players have met the winning condition.

Solution Approach

To solve the problem, we use a counting approach with the following steps:

Initialize Data Structures:
- We use a 2D list cnt where cnt[x][y] keeps track of how many balls of color y are picked by player x.
- We create a set s to store the IDs of players who win the game.
Process Each Ball Pick:
- Iterate through each element [x, y] in the pick list.
- For each pick, increment the count of cnt[x][y] by one.
Check Winning Condition:
- After updating the count, check if the number of balls of color y picked by player x (cnt[x][y]) exceeds x.
- If so, add player x to the set s. This ensures that we keep track of players who have met the winning condition.
Determine Result:
- The number of players who win the game is simply the size of the set s, as it contains the unique IDs of winning players.

By following these steps, we efficiently determine which players win based on the rules defined. The use of a set ensures that we do not overcount any player who meets the condition multiple times.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach:

Suppose n = 3 and the pick list is [[0, 1], [1, 2], [1, 2], [2, 3], [2, 3], [2, 3]].

Step 1: Initialize Data Structures

We need a count array cnt which tracks the number of balls of each color a player picks.
- Since n = 3, we'll have an array which can track up to three players.
Initialize an empty set s to store the IDs of players who meet the winning condition.

Step 2: Process Each Ball Pick

Process the picks in the order they appear:
1. For [0, 1]: Player 0 picks a ball of color 1.
  cnt[0][1] becomes 1.
  - Player 0 only needs to pick one ball to win. So, add 0 to set s.
2. For [1, 2]: Player 1 picks a ball of color 2.
  cnt[1][2] becomes 1.
  - Player 1 needs at least 2 balls of the same color, so no action.
3. For [1, 2]: Player 1 picks another ball of color 2.
  cnt[1][2] becomes 2.
  - Now, cnt[1][2] (2 balls) exceeds 1 (player index 1). Add 1 to s.
4. For [2, 3]: Player 2 picks a ball of color 3.
  cnt[2][3] becomes 1.
  - Player 2 needs at least 3 balls of the same color, so no action.
5. For [2, 3]: Player 2 picks another ball of color 3.
  cnt[2][3] becomes 2.
  - Still doesn't meet the required 3 balls, so no action.
6. For [2, 3]: Player 2 picks another ball of color 3.
  cnt[2][3] becomes 3.
  - cnt[2][3] (3 balls) exceeds 2 (player index 2). Add 2 to s.

Step 3: Determine Result

The set s now contains {0, 1, 2}, indicating that all three players have met their respective winning conditions.
Therefore, the number of players who win is the size of the set s, which is 3.

Solution Implementation

1from typing import List
2
3class Solution:
4    def winningPlayerCount(self, n: int, pick: List[List[int]]) -> int:
5        # Initialize a list of lists to count picks for each player at each position
6        count = [[0] * 11 for _ in range(n)]
7        winning_players = set()
8      
9        # Iterate over each pick in the list
10        for player, position in pick:
11            # Increment the count for the specified player and position
12            count[player][position] += 1
13          
14            # If the player selected this position more times than the player's index,
15            # they qualify as a 'winning player' and are added to the set
16            if count[player][position] > player:
17                winning_players.add(player)
18      
19        # The result is the number of winning players
20        return len(winning_players)
21

1import java.util.HashSet;
2import java.util.Set;
3
4class Solution {
5    public int winningPlayerCount(int n, int[][] pick) {
6        // cnt array stores counts of item picks for each player
7        int[][] cnt = new int[n][11];
8      
9        // Set to store players who "win"
10        Set<Integer> winningPlayers = new HashSet<>();
11      
12        // Iterate over each pick in the input
13        for (int[] p : pick) {
14            int playerIndex = p[0]; // player index (0-based)
15            int itemIndex = p[1];   // item index (1-based, assuming items range from 1 to 10)
16          
17            // Increment the count of picks for this player and item
18            if (++cnt[playerIndex][itemIndex] > playerIndex) {
19                // If the number of picks for this player and item exceeds the player's index,
20                // add the player to the winning set
21                winningPlayers.add(playerIndex);
22            }
23        }
24      
25        // Return the count of distinct winning players
26        return winningPlayers.size();
27    }
28}
29

1#include <vector>
2#include <unordered_set>
3
4class Solution {
5public:
6    int winningPlayerCount(int n, std::vector<std::vector<int>>& pick) {
7        // Initialize a count matrix with dimensions 10x11 set to zeros.
8        int count[10][11] = {}; 
9      
10        // Create an unordered set to hold the indices of winning players.
11        std::unordered_set<int> winningPlayers;
12      
13        // Iterate through each pick in the list of picks.
14        for (const auto& p : pick) {
15            int x = p[0]; // Extract the player index
16            int y = p[1]; // Extract the picked choice
17          
18            // Increment the count for the player x and choice y.
19            if (++count[x][y] > x) {
20                // If the count of a player's choice exceeds their index, they have won.
21                winningPlayers.insert(x);
22            }
23        }
24        // Return the number of unique winning players.
25        return winningPlayers.size();
26    }
27};
28

1function winningPlayerCount(n: number, pick: number[][]): number {
2    // Create a 2D array 'cnt' with dimensions 'n' by 11, initialized to 0.
3    // This will keep track of the number of times each player picks each number from 0 to 10.
4    const cnt: number[][] = Array.from({ length: n }, () => Array(11).fill(0));
5  
6    // Create a Set 's' to store unique player indices that meet the criteria.
7    const s = new Set<number>();
8
9    // Iterate over each pair [x, y] in 'pick'
10    for (const [x, y] of pick) {
11        // Increment the count for player 'x' picking number 'y'
12        if (++cnt[x][y] > x) {
13            // If the count exceeds the player's index 'x', add 'x' to the set 's'
14            s.add(x);
15        }
16    }
17
18    // Return the number of unique players that have been added to the set 's'
19    return s.size;
20}
21

Time and Space Complexity

The code iterates over the pick list, which consists of m elements. For each element in pick, a constant amount of work is performed—incrementing a counter and, potentially, updating a set. This results in a time complexity of O(m) for processing the pick list.

Additionally, initializing the cnt list involves constructing a two-dimensional list with dimensions n by M (11 in this case), which requires O(n \times M) operations. Thus, the total time complexity is O(m + n \times M).

For space complexity, the primary consideration is the cnt array, which holds n lists each containing M integers. This results in a space complexity of O(n \times M).

Other auxiliary space includes the s set, which, in the worst case, stores n elements, but this is dominated by the cnt array's space requirement.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which technique can we use to find the middle of a linked list?

Fast-slow pointers

Two pointers moving in opposite direction

Binary search

Depth first search

I don’t know