Find the Number of Winning Players

Difficulty: Easy | Acceptance: 60.50% | Paid: No Topics: Array, Hash Table, Counting

You are given a 2D integer array pick where pick[i] = [xi, yi] represents that the player xi picked a ball of color yi.

A player x is considered a winner if they have picked at least x balls of the same color.

Return the number of winning players.

• Examples
• Constraints
• Hash Map Frequency Count
• Array Simulation
• Sorting

Examples

Example 1:

Input: pick = [[0,1],[1,2],[1,2],[1,3]]
Output: 2
Explanation:
- Player 0 picked 1 ball of color 1. Since 1 >= 0, player 0 is a winner.
- Player 1 picked 2 balls of color 2. Since 2 >= 1, player 1 is a winner.
- Player 2 did not pick any balls.
Thus, there are 2 winning players.

Example 2:

Input: pick = [[1,1],[2,4],[2,4],[2,4]]
Output: 2
Explanation:
- Player 1 picked 1 ball of color 1. Since 1 >= 1, player 1 is a winner.
- Player 2 picked 3 balls of color 4. Since 3 >= 2, player 2 is a winner.
Thus, there are 2 winning players.

Example 3:

Input: pick = [[1,1],[1,2],[1,3],[2,4],[2,5]]
Output: 1
Explanation:
- Player 1 picked 1 ball of each color 1, 2, and 3. The maximum count is 1. Since 1 >= 1, player 1 is a winner.
- Player 2 picked 1 ball of each color 4 and 5. The maximum count is 1. Since 1 < 2, player 2 is not a winner.
Thus, there is 1 winning player.

Constraints

1 <= pick.length <= 100
0 <= xi, yi <= 10

Hash Map Frequency Count

Intuition We need to track how many balls of each color every player has picked. A hash map (or dictionary) mapping player IDs to another map of color counts allows us to efficiently aggregate this information.

Steps

• Initialize a hash map where keys are player IDs and values are hash maps of color counts.
• Iterate through the pick array. For each entry [x, y], increment the count of color y for player x.
• Iterate through the hash map. For each player, check if any of their color counts is greater than or equal to their player ID.
• If a player satisfies the condition, increment the result counter.

from collections import defaultdict

class Solution:
    def winningPlayerCount(self, pick: list[list[int]]) -> int:
        counts = defaultdict(lambda: defaultdict(int))
        for x, y in pick:
            counts[x][y] += 1
        
        winners = 0
        for player in counts:
            for color in counts[player]:
                if counts[player][color] > player:
                    winners += 1
                    break
        return winners

Complexity

• Time: O(n), where n is the length of pick. We iterate through the array once to build the map and once through the unique entries to check.
• Space: O(n), to store the frequency counts in the hash map.
• Notes: This approach is flexible and works for larger ranges of player IDs and colors.

Array Simulation

Intuition Given the constraints 0 <= xi, yi <= 10, the range of player IDs and colors is very small (0 to 10). We can use a fixed-size 2D array to store counts, which is faster and more memory-efficient than a hash map for this specific problem.

Steps

• Initialize a 2D array counts of size 11x11 with zeros.
• Iterate through pick. For each [x, y], increment counts[x][y].
• Iterate through the counts array. For each player i, check if any color count counts[i][j] is greater than i.
• Count the number of players who meet the criteria.

class Solution:
    def winningPlayerCount(self, pick: list[list[int]]) -> int:
        counts = [[0] * 11 for _ in range(11)]
        for x, y in pick:
            counts[x][y] += 1
        
        winners = 0
        for i in range(11):
            for j in range(11):
                if counts[i][j] > i:
                    winners += 1
                    break
        return winners

Complexity

• Time: O(n + 11²) which simplifies to O(n) since 11² is a constant.
• Space: O(11²) = O(1), constant space.
• Notes: This is the most optimal approach for the given constraints.

Sorting

Intuition We can sort the pick array first by player ID and then by color. This groups all picks for a specific player and color together, allowing us to count consecutive occurrences without extra space for a hash map.

Steps

• Sort the pick array based on player ID, then color.
• Iterate through the sorted array. For each segment of the same player and color, count the number of balls.
• If the count exceeds the player ID, mark the player as a winner and skip to the next player.
• Return the total count of winners.

class Solution:
    def winningPlayerCount(self, pick: list[list[int]]) -> int:
        pick.sort()
        winners = 0
        i = 0
        n = len(pick)
        while i < n:
            x = pick[i][0]
            j = i
            while j < n and pick[j][0] == x:
                j += 1
            
            k = i
            while k < j:
                y = pick[k][1]
                count = 0
                l = k
                while l < j and pick[l][1] == y:
                    count += 1
                    l += 1
                if count > x:
                    winners += 1
                    break
                k = l
            i = j
        return winners

Complexity

• Time: O(n log n) due to sorting.
• Space: O(1) or O(log n) depending on the sorting algorithm’s space complexity.
• Notes: This approach is less efficient than the hash map or array simulation due to the sorting step, but it avoids using extra data structures for counting.