Find the Number of Winning Players - Practice Coding Problems

Find the Number of Winning Players - Problem

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 (at least 1 ball of any color)
Player 1 wins if they pick at least 2 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.

Input & Output

Example 1 — Basic Game

$ Input: n = 4, pick = [[0,0],[1,0],[1,0],[2,1],[2,1],[2,0]]

› Output: 2

💡 Note: Player 0 picks 1 ball of color 0, needs ≥1, wins. Player 1 picks 2 balls of color 0, needs ≥2, wins. Player 2 picks 2 balls of color 1 and 1 of color 0, needs ≥3 of same color, loses. Player 3 picks nothing, loses.

Example 2 — Single Winner

$ Input: n = 5, pick = [[1,3],[4,4],[1,3],[3,0]]

› Output: 1

💡 Note: Player 1 picks 2 balls of color 3, needs ≥2, wins. Player 3 picks 1 ball of color 0, needs ≥4, loses. Player 4 picks 1 ball of color 4, needs ≥5, loses. Players 0 and 2 pick nothing, lose.

Example 3 — No Winners

$ Input: n = 3, pick = [[1,1],[2,2]]

› Output: 0

💡 Note: Player 0 picks nothing, loses. Player 1 picks 1 ball of color 1, needs ≥2, loses. Player 2 picks 1 ball of color 2, needs ≥3, loses.

Constraints

2 ≤ n ≤ 10
1 ≤ pick.length ≤ 100
pick[i].length == 2
0 ≤ x_i < n
0 ≤ y_i ≤ 10

Visualization

Tap to expand

Understanding the Visualization

Input

n=4 players, picks=[[0,0],[1,0],[1,0],[2,1],[2,1],[2,0]]

Process

Count each player's balls per color and check winning conditions

Output

2 players win the game

Key Takeaway

🎯 Key Insight: Player i needs at least i+1 balls of the same color to win

Asked in

G Google 15 M Microsoft 12 A Amazon 8

The key insight is that player i needs at least i+1 balls of the same color to win. Best approach uses frequency counting with nested maps to track each player's color picks in one pass, then checks winning conditions. Time: O(m + n), Space: O(n × colors).

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count - One Pass with Nested Maps	O(m + n)	O(n × colors)	Use nested hash maps to count picks per player-color combination
Brute Force - Check Each Player Individually	O(n × m)	O(colors)	For each player, count occurrences of each color they picked

Frequency Count - One Pass with Nested Maps — Algorithm Steps

Build nested map: player → color → count
For each player, find max count across all colors
Check if max count > player number

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Map

Count picks: player[0][1]=2, player[1][2]=2

Check Winners

For each player, find max color count

Result

Count players meeting winning condition

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int n, int pick[][2], int pickSize) {
    int playerColors[10][11];
    memset(playerColors, 0, sizeof(playerColors));
    
    for (int i = 0; i < pickSize; i++) {
        int player = pick[i][0];
        int color = pick[i][1];
        playerColors[player][color]++;
    }
    
    int winners = 0;
    for (int player = 0; player < n; player++) {
        int maxCount = 0;
        for (int color = 0; color <= 10; color++) {
            if (playerColors[player][color] > maxCount) {
                maxCount = playerColors[player][color];
            }
        }
        if (maxCount > player) {
            winners++;
        }
    }
    
    return winners;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[1000];
    scanf(" %s", line);
    
    int pick[100][2];
    int pickSize = 0;
    
    char* token = strtok(line, "[],");
    while (token != NULL) {
        if (strlen(token) > 0) {
            pick[pickSize / 2][pickSize % 2] = atoi(token);
            pickSize++;
        }
        token = strtok(NULL, "[],");
    }
    pickSize /= 2;
    
    printf("%d\n", solution(n, pick, pickSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m + n)

One pass through m picks plus one pass through n players

✓ Linear Growth

Space Complexity

O(n × colors)

Nested map storing counts for each player-color combination

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~12 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count - One Pass with Nested Maps — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler