Find the Number of Winning Players

EASY

Description

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

Checkout 2 different approaches to solve Find the Number of Winning Players. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Iteration

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.

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:

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 Analysis

Time Complexity: 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 Complexity: O(n) to store the `hasWon` boolean array.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find the Number of Winning Players. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Find the Number of Winning Players

Patterns:

Counting

Data Structures:

ArrayHash Table

Find the Number of Winning Players

Description

Approaches

Brute-Force Iteration

Algorithm

Complexity Analysis

Pros and Cons

Code Solutions

Video Solution

Similar Questions

Patterns:

Data Structures:

On this page

Subscribe to Scale Engineer newsletter