Scale Engineer

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
ArrayHash Table

Prompt

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 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 <= xi <= n - 1
  • 0 <= yi <= 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:

  1. We iterate through every player from 0 to n-1.
  2. For each player, we iterate through every possible color.
  3. For each player-color pair, we perform a full scan of the pick array to count the occurrences.
  4. If this count is greater than the player's index p, we've found a winning condition.
  5. 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:

class Solution {    public int numberOfWinners(int n, int[][] pick) {        int winners = 0;        boolean[] hasWon = new boolean[n];         // Iterate through each player        for (int p = 0; p < n; p++) {            // Iterate through each possible color            for (int c = 0; c <= 10; c++) { // Max color is 10                int count = 0;                // Scan the entire pick array to count                for (int[] currentPick : pick) {                    if (currentPick[0] == p && currentPick[1] == c) {                        count++;                    }                }                 // Check winning condition                if (count > p) {                    if (!hasWon[p]) {                        winners++;                        hasWon[p] = true;                    }                }            }        }        return winners;    }}

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.

Solutions

class Solution {public  int winningPlayerCount(int n, int[][] pick) {    int[][] cnt = new int[n][11];    Set<Integer> s = new HashSet<>();    for (var p : pick) {      int x = p[0], y = p[1];      if (++cnt[x][y] > x) {        s.add(x);      }    }    return s.size();  }}

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 →

Next problem