We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Number of Winning Players

Number: 3519

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given n players numbered from 0 to n - 1 and a 2D array pick where each element [x, y] represents that player x picked a ball of color y, determine how many players "win" the game. A player wins if they pick strictly more than i balls (i.e. at least i + 1 balls) of the same color. For example, player 0 wins if they pick any ball, while player 1 needs at least two balls of the same color, and so on.

Key Insights

  • Use a dictionary (or hash map) to track, for each player, the frequency of each ball color they picked.
  • The criteria for winning for player i is that at least one color appears at least i + 1 times.
  • Because n is small (2 <= n <= 10) and the length of pick is at most 100, a simple counting approach is efficient.
  • Edge case: Players who did not pick any ball (or no color reaches the required count) do not win.

Space and Time Complexity

Time Complexity: O(p) where p is the length of pick, since we traverse each pick once and then check counts for each player. Space Complexity: O(n * c) where c is the number of distinct colors (at most 11), used to store counts for each player.

Solution

The solution iterates over the pick array and updates a dictionary for each player mapping ball colors to their counts. After processing, each player’s dictionary is scanned to see if any color count meets or exceeds the required threshold (i + 1 for player i). The number of players meeting this condition is returned. The main data structure used is a hash table (dictionary) which allows constant-time updates and lookups for counts. This straightforward counting approach avoids unnecessary complications due to the small constraints, making it both intuitive and efficient.

Code Solutions

# Python solution to count the number of winning players

def findWinners(n, pick):
    # Create a list of dictionaries to store counts for each player.
    player_counts = [{} for _ in range(n)]
    
    # Process each pick and update the count for the corresponding player and color.
    for player, color in pick:
        # Initialize the count for the color if not already present.
        if color not in player_counts[player]:
            player_counts[player][color] = 0
        # Increment the count for the picked color.
        player_counts[player][color] += 1
        
    winners = 0
    # Check each player's counts to determine if they win.
    for i in range(n):
        # The winning threshold for player i is i + 1 balls of the same color.
        required = i + 1
        # Check all colors counts for player i.
        for count in player_counts[i].values():
            if count >= required:
                winners += 1
                break  # No need to check further for this player.
    
    return winners

# Example usage:
print(findWinners(4, [[0,0],[1,0],[1,0],[2,1],[2,1],[2,0]]))  # Output: 2
← Back to All Questions