Problem

You are given a collection of numbered balls and instructed to sort them into boxes for a nearly balanced distribution. There are two rules you must follow:

  • Balls with the same box must have the same value. But, if you have more than one ball with the same number, you can put them in different boxes.
  • The biggest box can only have one more ball than the smallest box.

​Return the fewest number of boxes to sort these balls following these rules.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


Input: balls = [3,2,3,2,3]

Output: 2

Explanation:

We can sort `balls` into boxes as follows:

  * `[3,3,3]`
  * `[2,2]`

The size difference between the two boxes doesn't exceed one.

Example 2

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


Input: balls = [10,10,10,3,1,1]

Output: 4

Explanation:

We can sort `balls` into boxes as follows:

  * `[10]`
  * `[10,10]`
  * `[3]`
  * `[1,1]`

You can't use fewer than four boxes while still following the rules. For
example, putting all three balls numbered 10 in one box would break the rule
about the maximum size difference between boxes.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

Solution

Method 1 – Greedy Frequency Grouping

Intuition

For each value, split its balls into groups of size ⌈count/boxes⌉, so that the largest and smallest box differ by at most one. The minimum number of boxes is the maximum frequency among all values.

Approach

  1. Count the frequency of each value.
  2. The answer is the maximum frequency among all values.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    int minGroups(vector<int>& balls) {
        unordered_map<int, int> freq;
        for (int x : balls) freq[x]++;
        int ans = 0;
        for (auto& [_, f] : freq) ans = max(ans, f);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9

func minGroups(balls []int) int {
    freq := map[int]int{}
    for _, x := range balls { freq[x]++ }
    ans := 0
    for _, f := range freq {
        if f > ans { ans = f }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

import java.util.*;
class Solution {
    public int minGroups(int[] balls) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : balls) freq.put(x, freq.getOrDefault(x, 0) + 1);
        int ans = 0;
        for (int f : freq.values()) ans = Math.max(ans, f);
        return ans;
    }
}
1
2
3
4
5
6
7

class Solution {
    fun minGroups(balls: IntArray): Int {
        val freq = mutableMapOf<Int, Int>()
        for (x in balls) freq[x] = freq.getOrDefault(x, 0) + 1
        return freq.values.maxOrNull() ?: 0
    }
}
1
2
3
4
5

from collections import Counter
class Solution:
    def minGroups(self, balls: list[int]) -> int:
        freq = Counter(balls)
        return max(freq.values())
1
2
3
4
5
6
7
8

use std::collections::HashMap;
impl Solution {
    pub fn min_groups(balls: Vec<i32>) -> i32 {
        let mut freq = HashMap::new();
        for x in balls { *freq.entry(x).or_insert(0) += 1; }
        *freq.values().max().unwrap()
    }
}
1
2
3
4
5
6
7

class Solution {
    minGroups(balls: number[]): number {
        const freq = new Map<number, number>();
        for (const x of balls) freq.set(x, (freq.get(x) ?? 0) + 1);
        return Math.max(...freq.values());
    }
}

Complexity

  • ⏰ Time complexity: O(n) — n = length of balls.
  • 🧺 Space complexity: O(n) — for frequency map.