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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Number of Winning Players

Difficulty: Easy

Problem 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. Return the number of players who win the game.

Key Insights

  • Each player has a specific requirement to win based on their player index.
  • We need to count the occurrences of each color picked by each player.
  • A player wins if they have more balls of a particular color than their index.
  • The solution can be implemented using a hash table (dictionary) to track counts.

Space and Time Complexity

Time Complexity: O(m), where m is the number of picks. Space Complexity: O(n * k), where n is the number of players and k is the number of colors.

Solution

To solve this problem, we can maintain a dictionary to count the occurrences of each color for each player. We will iterate through the pick list and populate this dictionary. After counting, we will check for each player if their count for any color exceeds their winning condition (i.e., player i needs more than i of any color). Finally, we will return the count of players who meet their winning condition.

Code Solutions

def countWinningPlayers(n, pick):
    from collections import defaultdict
    
    # Dictionary to hold counts of balls picked by each player
    color_count = defaultdict(lambda: defaultdict(int))
    
    # Count the balls picked by each player
    for player, color in pick:
        color_count[player][color] += 1
    
    winning_players = 0
    
    # Check winning conditions for each player
    for player in range(n):
        for count in color_count[player].values():
            if count > player:
                winning_players += 1
                break  # No need to check further colors for this player
    
    return winning_players
← Back to All Questions