Find the Number of Winning Players

Easy

#2875Time: O(n * C * L), where `n` is the number of players, `C` is the number of possible colors (11 in this case), and `L` is the length of the `pick` array. The three nested loops dominate the runtime.Space: O(n) to store the `hasWon` boolean array.

Patterns

Counting

Data structures

Array Hash Table

Prompt

You are given an integer n representing the number of players in a game and a 2D array pick where pick[i] = [x_i, y_i] represents that the player x_i picked a ball of color y_i.

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 least i + 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 <= x_i <= n - 1
0 <= y_i <= 10

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. It iterates through each player and, for each player, iterates through all possible colors. For each player-color combination, it scans the entire pick array to count how many balls of that color the player has picked. If this count exceeds the player's index, the player is marked as a winner.

Algorithm

Initialize a counter for winning players, winners, to 0.
Create a boolean array, hasWon, of size n to track which players have already been counted as winners.
Loop through each player p from 0 to n-1.
Inside this loop, loop through each possible color c (from 0 to 10, based on constraints).
For each (p, c) pair, initialize a count to 0.
Iterate through the pick array. If an entry [player, color] matches (p, c), increment count.
After counting, check if count > p.
If the condition is true and hasWon[p] is false, it means player p is a winner. Increment winners and set hasWon[p] to true.
After all loops complete, return winners.

Walkthrough

This method involves a straightforward, yet inefficient, triple-nested loop structure. The logic is as follows:

We iterate through every player from 0 to n-1.
For each player, we iterate through every possible color.
For each player-color pair, we perform a full scan of the pick array to count the occurrences.
If this count is greater than the player's index p, we've found a winning condition.
A boolean array hasWon is used to ensure we only count each winning player once, even if they meet the winning criteria with multiple colors.

Here is the Java implementation:

1class Solution {2    public int numberOfWinners(int n, int[][] pick) {3        int winners = 0;4        boolean[] hasWon = new boolean[n];5 6        // Iterate through each player7        for (int p = 0; p < n; p++) {8            // Iterate through each possible color9            for (int c = 0; c <= 10; c++) { // Max color is 1010                int count = 0;11                // Scan the entire pick array to count12                for (int[] currentPick : pick) {13                    if (currentPick[0] == p && currentPick[1] == c) {14                        count++;15                    }16                }17 18                // Check winning condition19                if (count > p) {20                    if (!hasWon[p]) {21                        winners++;22                        hasWon[p] = true;23                    }24                }25            }26        }27        return winners;28    }29}

Complexity

Time

O(n * C * L), where `n` is the number of players, `C` is the number of possible colors (11 in this case), and `L` is the length of the `pick` array. The three nested loops dominate the runtime.

Space

O(n) to store the `hasWon` boolean array.

Trade-offs

Pros

Simple to understand and implement directly from the problem definition.

Cons

Highly inefficient due to repeated scanning of the pick array.
For larger inputs, this would be too slow.

This approach improves upon the brute-force method by pre-processing the pick array to efficiently count the balls for each player. It uses a 2D array to store the counts of each color for each player. This avoids re-scanning the pick array repeatedly. After counting, it iterates through the players to check the winning condition against the stored counts.

Algorithm

Create a 2D array, counts, of size n x 11 (for n players and 11 possible colors 0-10), initialized to zeros. This will store counts[player][color].
Iterate through the pick array once. For each entry [player, color], increment counts[player][color].
Initialize a counter for winning players, winners, to 0.
Loop through each player p from 0 to n-1.
For each player p, loop through each color c from 0 to 10.
Check if counts[p][c] > p.
If the condition is true, player p is a winner. Increment winners and break the inner color loop to proceed to the next player (as we only count each player once).
After the loops complete, return winners.

Walkthrough

This optimized approach avoids redundant computations by first aggregating all the pick data into a more suitable data structure. A 2D array is a perfect choice given the small and fixed ranges for player IDs and colors.

The process is divided into two main phases:

Counting Phase: We iterate through the pick array just once. For each pick [player, color], we increment a counter in our 2D array counts[player][color]. This phase populates our counts array in linear time with respect to the number of picks.
Checking Phase: After all counts are gathered, we iterate through each player p. For each player, we check their counts for all possible colors. If we find any color c where counts[p][c] is greater than p, we know the player has won. We increment our winner count and immediately break from the inner loop to check the next player, preventing double counting.

Here is the Java implementation:

1class Solution {2    public int numberOfWinners(int n, int[][] pick) {3        // counts[player][color] stores the number of balls of that color picked by the player.4        // Constraints: n <= 10, color <= 10.5        int[][] counts = new int[n][11];6 7        // 1. Counting Phase8        for (int[] p : pick) {9            int player = p[0];10            int color = p[1];11            counts[player][color]++;12        }13 14        int winners = 0;15        // 2. Checking Phase16        for (int p = 0; p < n; p++) {17            for (int c = 0; c <= 10; c++) {18                // Winning condition: picked strictly more than p balls of the same color.19                if (counts[p][c] > p) {20                    winners++;21                    break; // Player p has won, move to the next player.22                }23            }24        }25        return winners;26    }27}

Complexity

Time

O(L + n * C), where `L` is the length of the `pick` array, `n` is the number of players, and `C` is the number of possible colors (11). We iterate through `pick` once (`O(L)`) and then check the counts for each player and color (`O(n * C)`).

Space

O(n * C) to store the `counts` in the 2D array, where C is the number of colors.

Trade-offs

Pros

Significantly more efficient than the brute-force approach.
Processes the input pick array only once.

Cons

Requires extra space for the counts data structure, but this is minimal given the problem constraints.

Solutions

Solution

1class Solution {2public3  int winningPlayerCount(int n, int[][] pick) {4    int[][] cnt = new int[n][11];5    Set<Integer> s = new HashSet<>();6    for (var p : pick) {7      int x = p[0], y = p[1];8      if (++cnt[x][y] > x) {9        s.add(x);10      }11    }12    return s.size();13  }14}

1class Solution {2public:3  int winningPlayerCount(int n, vector<vector<int>> &pick) {4    int cnt[10][11]{};5    unordered_set<int> s;6    for (const auto &p : pick) {7      int x = p[0], y = p[1];8      if (++cnt[x][y] > x) {9        s.insert(x);10      }11    }12    return s.size();13  }14};

1class Solution:2    def winningPlayerCount(self, n: int, pick: List[List[int]]) -> int: cnt = [[0] * 11 for _ in range(n)] s = set() for x, y in pick: cnt[x][y] += 1 if cnt[x][y] > x: s . add(x) return len(s)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int winningPlayerCount(int n, int[][] pick) {4    int[][] cnt = new int[n][11];5    Set<Integer> s = new HashSet<>();6    for (var p : pick) {7      int x = p[0], y = p[1];8      if (++cnt[x][y] > x) {9        s.add(x);10      }11    }12    return s.size();13  }14}

1class Solution {2public:3  int winningPlayerCount(int n, vector<vector<int>> &pick) {4    int cnt[10][11]{};5    unordered_set<int> s;6    for (const auto &p : pick) {7      int x = p[0], y = p[1];8      if (++cnt[x][y] > x) {9        s.insert(x);10      }11    }12    return s.size();13  }14};

1class Solution:2    def winningPlayerCount(self, n: int, pick: List[List[int]]) -> int: cnt = [[0] * 11 for _ in range(n)] s = set() for x, y in pick: cnt[x][y] += 1 if cnt[x][y] > x: s . add(x) return len(s)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.