Skip to main content
Talentd

Find the Number of Winning Players - Solution & Explanation

EasyArrayHash TableCounting16 min readAsked at: Google
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given n players and a list of ball picks where picks[i] = [player, color]. A player i wins if they collect strictly more than i balls of the same color. The task is to count how many players satisfy this winning condition.

Approach 1: Hash Map Approach (O(m) time, O(m) space)

Track how many balls of each color every player collects. Use a hash map keyed by (player, color) and increment the count while iterating through the picks array. Whenever the count for a pair exceeds the player's index player, mark that player as a winner. A set helps ensure each player is counted only once even if multiple colors exceed the threshold.

This approach works well when the number of colors is large or unknown. Hash lookups keep updates constant time, making the entire scan of picks linear. The technique relies on efficient frequency tracking using a hash table and simple counting.

Approach 2: Array Counting Approach (O(m) time, O(n * c) space)

If the number of colors is small or bounded, replace the hash map with a 2D counting array where count[player][color] stores how many balls of that color the player has picked. Iterate through picks, increment the corresponding cell, and check whether the count becomes greater than the player's index. Maintain a boolean array to mark winners so each player contributes to the result once.

This approach avoids hashing overhead and uses direct indexing. It performs well when color IDs are within a predictable range, making array access faster than map operations. The method is essentially a structured version of the same array frequency counting pattern.

Recommended for interviews: The hash map approach is typically expected because it works for any color range without assumptions. The array counting version is a good optimization when constraints guarantee small color values. Showing both demonstrates you understand frequency counting tradeoffs and space optimization.

Approach 1: Hash Map Approach

In this approach, we make use of a two-dimensional hash map. For each pick (where a player picks a ball of a certain color), we increment the count in our hash map. Once all picks are processed, we check each player to determine if they have picked more than the required number of balls of the same color to win.

This solution uses a list of dictionaries, where each dictionary corresponds to a player. The keys of the dictionary are the colors, and the values are the counts of that color picked by the player. We iterate through each player's dictionary and check if any color has been picked more times than required. If so, we increment the count of winning players.

Code

PythonJavaC++JavaScriptCC#

Python

Java

C++

JavaScript

C

C#

Complexity

Time Complexity: O(p) where p is the number of entries in the 'pick' list.

Space Complexity: O(n * c) where n is the number of players and c is the number of colors.

Try this approach in the editor →

Approach 2: Array Counting Approach

This method involves using a simple array structure to count the number of balls each player has picked by color, taking advantage of maximum constraints. This reduces overhead but is less flexible than hash maps.

This solution predefines a fixed-size array to count ball colors for each player based on constraints. This keeps memory usage predictable and direct, by leveraging the small number of players and colors specified in the problem constraints.

Code

PythonJavaC++JavaScriptCC#

Python

Java

C++

JavaScript

C

C#

Complexity

Time Complexity: O(p), where p is the number of picks.

Space Complexity: O(n * 10) = O(n), due to known constraints with up to 11 colors and n players.

Try this approach in the editor →

Approach 3: Counting

We can use a 2D array cnt to record the number of balls of each color obtained by each player, and a hash table s to record the IDs of the winning players.

Traverse the pick array, for each element [x, y], we increment cnt[x][y] by one. If cnt[x][y] is greater than x, we add x to the hash table s.

Finally, return the size of the hash table 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 pick array, and n and M are the number of players and the number of colors, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Hash Map Approach

Time Complexity: O(p) where p is the number of entries in the 'pick' list.

Space Complexity: O(n * c) where n is the number of players and c is the number of colors.

Array Counting Approach

Time Complexity: O(p), where p is the number of picks.

Space Complexity: O(n * 10) = O(n), due to known constraints with up to 11 colors and n players.

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map CountingO(m)O(m)General case where color range is unknown or large
Array CountingO(m)O(n * c)When the color range is small and direct indexing is possible

Video Solution

Find the Number of Winning Players || Biweekly Contest 136 || Leetcode Solution • codi • 1,303 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Find the Number of Winning Players easy or hard?
Find the Number of Winning Players is classified as an Easy problem. It mainly tests understanding of hash maps, frequency counting, and simple conditional checks rather than complex algorithms.
Find the Number of Winning Players Python/Java solution
In Python or Java, iterate through the picks list and update a hash map keyed by (player, color). When the count exceeds the player index, mark that player as a winner. FleetCode provides full implementations in Python, Java, C++, JavaScript, C, and C#.
How to solve Find the Number of Winning Players in O(n)?
Iterate through the picks array once while maintaining frequency counts of (player, color). When the count for a pair becomes greater than the player index, record that player as a winner using a set or boolean array. This single pass produces an O(m) time solution with constant‑time updates.
What is the best approach for Find the Number of Winning Players?
The hash map counting approach is the most flexible solution. It tracks the number of balls for each (player, color) pair and checks when the count exceeds the player's index. This runs in O(m) time where m is the number of picks and works even when color values are large.
Is Find the Number of Winning Players asked at Google/Amazon/Meta?
Problems based on frequency counting with hash maps and arrays commonly appear in coding interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying pattern of tracking counts and applying thresholds is frequently tested.
What data structure is used in Find the Number of Winning Players?
The most common data structures are a hash map for frequency counting and a set or boolean array to track players who already won. An alternative implementation uses a 2D array where indices represent players and colors.
What is the time complexity of Find the Number of Winning Players?
The optimal solution runs in O(m) time, where m is the number of picks in the input. Each pick updates a frequency counter and performs a constant‑time comparison. Space complexity is O(m) for the hash map or O(n * c) when using an array counting structure.

Ready to solve this problem?

Practice Find the Number of Winning Players with our built-in code editor and test cases.

Practice on FleetCode
Previous

Can I Win

Next

Predict the Winner