LeetCode 3238 - Find the Number of Winning Players

The problem gives us n players and a list called pick, where each entry is of the form [xi, yi]. This means player xi picked a ball with color yi. A player wins if they have picked strictly more than their player index number of balls of the same color.

leetcodeeasyarrayhash-tablecounting

LeetCode Problem 3238

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Counting

Solution

LeetCode 3238 - Find the Number of Winning Players

Problem Understanding

The problem gives us n players and a list called pick, where each entry is of the form [xi, yi]. This means player xi picked a ball with color yi.

A player wins if they have picked strictly more than their player index number of balls of the same color.

This condition can be rewritten more clearly:

  • Player 0 wins if they have at least 1 ball of any single color.
  • Player 1 wins if they have at least 2 balls of the same color.
  • Player 2 wins if they have at least 3 balls of the same color.
  • In general, player i wins if some color appears at least i + 1 times among their picks.

The task is to count how many players satisfy this condition.

The input size is very small:

  • n <= 10
  • pick.length <= 100
  • yi <= 10

These constraints immediately suggest that performance is not a major concern. Even relatively inefficient approaches would still run comfortably within limits. However, we still want to design a clean and logically efficient solution.

The important observation is that the winning condition depends on the frequency of a single color for each player. We do not care about the total number of balls a player picked unless many of them share the same color.

Some important edge cases include:

  • A player picking many balls, but all with different colors, does not necessarily win.
  • Player 0 wins as soon as they pick any ball because they only need more than 0.
  • A player may have multiple colors meeting the condition, but they should still only be counted once.
  • Some players may never appear in pick, meaning they automatically lose.

Approaches

Brute Force Approach

A straightforward brute-force solution would examine every player individually and count how many times each color appears for that player.

One possible brute-force strategy is:

  1. For each player i
  2. For every possible color
  3. Scan the entire pick array
  4. Count how many times player i picked that color
  5. Check whether the count exceeds i

This works because it directly checks the definition of winning.

However, this approach repeatedly scans the entire pick array for every player and color combination. Even though the constraints are small, this involves unnecessary repeated work.

Optimal Approach

The better solution is to process the pick array once while maintaining frequency counts.

The key insight is that the problem only requires counting how many times each player picked each color. A hash map is ideal for this because:

  • Players are small integers
  • Colors are small integers
  • We need frequency counting

We can build a nested frequency table:

player -> color -> count

As we process each pick, we increment the corresponding count.

After building the frequency table, we iterate through each player’s color counts and check whether any color frequency exceeds the player index.

This avoids repeatedly rescanning the input and keeps the logic simple and clean.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × c × m) O(1) Repeatedly scans all picks for every player and color
Optimal O(m + total_counts) O(m) Uses hash maps to store frequencies efficiently

Where:

  • m = len(pick)
  • c = number of possible colors

Since colors are bounded by 11, both approaches are acceptable here, but the hash map solution is more scalable and cleaner.

Algorithm Walkthrough

  1. Create a frequency structure to track how many times each player picked each color.

We use a nested hash map:

counts[player][color] = frequency

This lets us update and query frequencies efficiently. 2. Traverse the pick array once.

For each [player, color] pair:

  • Increase the count for that player's color.

Example:

counts[2][4] += 1
  1. Initialize a variable winning_players = 0.

This will store the number of players who satisfy the winning condition. 4. Iterate through every player’s color frequencies.

For each player:

  • Check every color count.
  • If any count is greater than the player index, that player wins.
  1. Once a player is confirmed as a winner, stop checking additional colors for that player.

We only count each player once. 6. Return the final count.

Why it works

The algorithm correctly computes the frequency of every color chosen by every player. A player wins if at least one color frequency exceeds the player index. Since the algorithm checks exactly this condition for every player, the result is guaranteed to be correct.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def winningPlayerCount(self, n: int, pick: List[List[int]]) -> int:
        counts = defaultdict(lambda: defaultdict(int))

        # Count how many times each player picked each color
        for player, color in pick:
            counts[player][color] += 1

        winning_players = 0

        # Check whether each player has a winning color
        for player in counts:
            for frequency in counts[player].values():
                if frequency > player:
                    winning_players += 1
                    break

        return winning_players

The implementation begins by importing defaultdict, which simplifies frequency counting. The nested defaultdict structure automatically initializes missing entries to zero.

During the first loop, every pick updates the frequency table. After this preprocessing step, all required information is available.

The second phase checks each player independently. For every player, we inspect the frequencies of all colors they picked. If any frequency exceeds the player index, that player is counted as a winner.

The break statement is important because a player should only be counted once, even if multiple colors satisfy the condition.

Go Solution

func winningPlayerCount(n int, pick [][]int) int {
	counts := make(map[int]map[int]int)

	// Count frequencies
	for _, p := range pick {
		player := p[0]
		color := p[1]

		if counts[player] == nil {
			counts[player] = make(map[int]int)
		}

		counts[player][color]++
	}

	winningPlayers := 0

	// Check winning condition
	for player, colorCounts := range counts {
		for _, frequency := range colorCounts {
			if frequency > player {
				winningPlayers++
				break
			}
		}
	}

	return winningPlayers
}

The Go implementation follows the same logic as the Python solution.

Since Go does not have a built-in nested default dictionary, we explicitly initialize inner maps when needed.

The frequency counting and winner checking logic remain identical. Go maps return zero values for missing keys, which makes frequency increments straightforward after initialization.

Integer overflow is not a concern because all counts are very small under the given constraints.

Worked Examples

Example 1

Input:

n = 4
pick = [[0,0],[1,0],[1,0],[2,1],[2,1],[2,0]]

Step 1: Build frequency table

Pick Frequency State
[0,0] player 0: {0:1}
[1,0] player 1: {0:1}
[1,0] player 1: {0:2}
[2,1] player 2: {1:1}
[2,1] player 2: {1:2}
[2,0] player 2: {1:2, 0:1}

Final structure:

player 0 -> {0:1}
player 1 -> {0:2}
player 2 -> {1:2, 0:1}

Step 2: Check winners

Player Required Frequency Actual Frequencies Wins?
0 > 0 1 Yes
1 > 1 2 Yes
2 > 2 2, 1 No

Answer:

2

Example 2

Input:

n = 5
pick = [[1,1],[1,2],[1,3],[1,4]]

Frequency table:

player 1 -> {
    1:1,
    2:1,
    3:1,
    4:1
}

Player 1 needs more than 1 occurrence of the same color.

All frequencies are only 1.

No player wins.

Answer:

0

Example 3

Input:

n = 5
pick = [[1,1],[2,4],[2,4],[2,4]]

Frequency table:

player 1 -> {1:1}
player 2 -> {4:3}

Winner check

Player Required Frequency Actual Frequency Wins?
1 > 1 1 No
2 > 2 3 Yes

Answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(m) Each pick is processed once, and each stored frequency is checked once
Space O(m) In the worst case, all picks create unique player-color entries

Here, m is the length of the pick array.

The algorithm is linear with respect to the number of picks because frequency counting and winner checking both require only a single traversal of the stored data.

Test Cases

from typing import List
from collections import defaultdict

class Solution:
    def winningPlayerCount(self, n: int, pick: List[List[int]]) -> int:
        counts = defaultdict(lambda: defaultdict(int))

        for player, color in pick:
            counts[player][color] += 1

        winning_players = 0

        for player in counts:
            for frequency in counts[player].values():
                if frequency > player:
                    winning_players += 1
                    break

        return winning_players

sol = Solution()

# Provided examples
assert sol.winningPlayerCount(
    4,
    [[0, 0], [1, 0], [1, 0], [2, 1], [2, 1], [2, 0]]
) == 2  # Example 1

assert sol.winningPlayerCount(
    5,
    [[1, 1], [1, 2], [1, 3], [1, 4]]
) == 0  # Example 2

assert sol.winningPlayerCount(
    5,
    [[1, 1], [2, 4], [2, 4], [2, 4]]
) == 1  # Example 3

# Player 0 wins with a single pick
assert sol.winningPlayerCount(
    2,
    [[0, 5]]
) == 1  # Minimum winning condition

# No players appear
assert sol.winningPlayerCount(
    3,
    []
) == 0  # Empty pick list

# Multiple winning players
assert sol.winningPlayerCount(
    4,
    [[0, 1], [1, 2], [1, 2], [2, 3], [2, 3], [2, 3]]
) == 3  # Players 0, 1, and 2 win

# Many colors but insufficient duplicates
assert sol.winningPlayerCount(
    3,
    [[2, 1], [2, 2], [2, 3], [2, 4]]
) == 0  # No color appears enough times

# Multiple qualifying colors for one player
assert sol.winningPlayerCount(
    3,
    [[1, 1], [1, 1], [1, 2], [1, 2]]
) == 1  # Count player once only

# Highest player index wins exactly at threshold + 1
assert sol.winningPlayerCount(
    5,
    [[4, 7], [4, 7], [4, 7], [4, 7], [4, 7]]
) == 1  # Player 4 needs 5 identical colors
Test Why
Example 1 Validates normal mixed behavior
Example 2 Ensures different colors do not combine counts
Example 3 Verifies larger frequency threshold
Single pick for player 0 Tests smallest winning condition
Empty pick list Confirms no crashes on empty input
Multiple winners Verifies counting several winners correctly
Distinct colors only Ensures duplicates are required
Multiple winning colors Confirms a player is counted once
Player 4 with five identical colors Tests higher threshold logic

Edge Cases

Player 0 Requires Only One Ball

Player 0 is special because the winning condition is frequency greater than 0. That means a single occurrence of any color is enough.

This can easily cause off-by-one mistakes if the condition is implemented incorrectly as >= player instead of > player.

The implementation handles this correctly by checking:

if frequency > player

For player 0, any frequency of 1 satisfies the condition.

Many Picks but No Repeated Colors

A player may pick many balls without winning if no color appears frequently enough.

For example:

player 2 -> colors [1,2,3,4]

Even though the player picked four balls total, each color frequency is only 1, which is not enough.

The implementation correctly checks frequencies individually rather than total pick count.

A Player Qualifies with Multiple Colors

A player may satisfy the winning condition for more than one color.

For example:

player 1 -> {2:2, 3:2}

The player should still only count once.

The implementation avoids double counting by using break immediately after finding the first qualifying color.