Problem

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 leasti + 1 balls of the same color.

Return the number of players who win the game.

Note that multiple players can win the game.

Examples

Example 1

1
2
3
4
5
6
7
8


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

1
2
3
4
5
6
7
8


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

Output: 0

Explanation:

No player wins the game.

Example 3

1
2
3
4
5
6
7
8


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

Solution

Method 1 – Counting by Player and Color

Intuition

For each player, count how many balls of each color they picked. If any color count is greater than the player’s index, the player wins. This is a direct application of the problem’s definition.

Approach

  1. For each player, use a hash map (or array) to count the number of balls picked for each color.
  2. For each player, check if any color count is greater than the player’s index.
  3. Count the number of players who satisfy the winning condition.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int numberOfWinners(int n, vector<vector<int>>& pick) {
        vector<unordered_map<int, int>> cnt(n);
        for (auto& p : pick) cnt[p[0]][p[1]]++;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (auto& [color, c] : cnt[i]) {
                if (c > i) {
                    ans++;
                    break;
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func numberOfWinners(n int, pick [][]int) int {
    cnt := make([]map[int]int, n)
    for i := range cnt {
        cnt[i] = map[int]int{}
    }
    for _, p := range pick {
        cnt[p[0]][p[1]]++
    }
    ans := 0
    for i := 0; i < n; i++ {
        for _, c := range cnt[i] {
            if c > i {
                ans++
                break
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int numberOfWinners(int n, int[][] pick) {
        Map<Integer, Integer>[] cnt = new HashMap[n];
        for (int i = 0; i < n; ++i) cnt[i] = new HashMap<>();
        for (int[] p : pick) cnt[p[0]].put(p[1], cnt[p[0]].getOrDefault(p[1], 0) + 1);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int c : cnt[i].values()) {
                if (c > i) {
                    ans++;
                    break;
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun numberOfWinners(n: Int, pick: Array<IntArray>): Int {
        val cnt = Array(n) { mutableMapOf<Int, Int>() }
        for (p in pick) cnt[p[0]][p[1]] = cnt[p[0]].getOrDefault(p[1], 0) + 1
        var ans = 0
        for (i in 0 until n) {
            if (cnt[i].values.any { it > i }) ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def numberOfWinners(self, n: int, pick: list[list[int]]) -> int:
        cnt = [{} for _ in range(n)]
        for x, y in pick:
            cnt[x][y] = cnt[x].get(y, 0) + 1
        ans = 0
        for i in range(n):
            if any(c > i for c in cnt[i].values()):
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn number_of_winners(n: i32, pick: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut cnt = vec![std::collections::HashMap::new(); n];
        for p in pick {
            *cnt[p[0] as usize].entry(p[1]).or_insert(0) += 1;
        }
        let mut ans = 0;
        for (i, m) in cnt.iter().enumerate() {
            if m.values().any(|&c| c > i) {
                ans += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    numberOfWinners(n: number, pick: number[][]): number {
        const cnt: Record<number, Record<number, number>> = {};
        for (let i = 0; i < n; ++i) cnt[i] = {};
        for (const [x, y] of pick) cnt[x][y] = (cnt[x][y] || 0) + 1;
        let ans = 0;
        for (let i = 0; i < n; ++i) {
            if (Object.values(cnt[i]).some(c => c > i)) ans++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * m) — For each pick and each player, where m is the number of picks.
  • 🧺 Space complexity: O(n * c) — For the color counts per player, where c is the number of colors.