Minimum Number of Groups to Create a Valid Assignment

Medium
1449.

Minimum Number of Groups to Create a Valid Assignment

Minimum Number of Groups to Create a Valid Assignment is a medium coding problem on arrays, hash table and greedy, asked in Amazon and Google interviews.

The CodeKairo swag room has a pile of numbered balls; balls[i] is the number printed on the i-th ball. Every ball must go into a box, following two rules:

  • All balls inside one box carry the same number (balls with the same number may still be spread over several boxes).
  • The fullest box holds at most one ball more than the emptiest box.

Return the fewest boxes needed.

Example 1

Input
balls = [3,2,3,2,3]
Output
2
Explanation
One box with the three 3s and one box with the two 2s: sizes 3 and 2 differ by one.

Example 2

Input
balls = [10,10,10,3,1,1]
Output
4
Explanation
The lone 3 forces boxes of size 1 or 2: `[10,10]`, `[10]`, `[3]`, `[1,1]`.

Example 3

Input
balls = [7,7,7,7,7,7,7,1,1,1]
Output
3
Explanation
Boxes of sizes 3 or 4: the seven 7s fill a box of 4 and a box of 3, the three 1s fill one box of 3.

Constraints

  • 1 <= balls.length <= 10^5
  • 1 <= balls[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} balls
 * @return {number}
 */
var minGroupsForValidAssignment = function(balls) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Groups to Create a Valid Assignment Solution

Minimum Number of Groups to Create a Valid Assignment solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Number of Groups to Create a Valid Assignment is a medium coding problem on arrays, hash table and greedy, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Greedy
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

The CodeKairo swag room has a pile of numbered balls; balls[i] is the number printed on the i-th ball. Every ball must go into a box, following two rules:

  • All balls inside one box carry the same number (balls with the same number may still be spread over several boxes).
  • The fullest box holds at most one ball more than the emptiest box.

Return the fewest boxes needed.

Example 1

Input: balls = [3,2,3,2,3]
Output: 2
Explanation: One box with the three 3s and one box with the two 2s: sizes 3 and 2 differ by one.

Example 2

Input: balls = [10,10,10,3,1,1]
Output: 4
Explanation: The lone 3 forces boxes of size 1 or 2: `[10,10]`, `[10]`, `[3]`, `[1,1]`.

Example 3

Input: balls = [7,7,7,7,7,7,7,1,1,1]
Output: 3
Explanation: Boxes of sizes 3 or 4: the seven 7s fill a box of 4 and a box of 3, the three 1s fill one box of 3.

Constraints

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

Hints for Minimum Number of Groups to Create a Valid Assignment

  1. Hint 1

    Only how many times each number occurs matters, not the numbers themselves.

  2. Hint 2

    If the smallest box holds k balls, every box holds k or k + 1, and k can be at most the rarest number's count.

  3. Hint 3

    For a fixed k, a count c needs g = ceil(c / (k + 1)) boxes and works only if g * k <= c. Try k from the largest value down; the first k that works for every count gives the answer.

How to solve Minimum Number of Groups to Create a Valid Assignment

Fix the size k of the smallest box. Every box then holds k or k + 1 balls, each number's balls can be packed independently, and a larger k never needs more boxes — so the largest feasible k wins.

Approach

  1. Count the occurrences of each number; let m be the smallest count.
  2. For k from m down to 1: for each count c, take g = ceil(c / (k + 1)) boxes — the fewest that can hold c balls at k + 1 each.
  3. Those g boxes can hold anything from g * k to g * (k + 1) balls, so the count fits exactly when g * k <= c. If every count fits, return the sum of the gs.
  4. k = 1 always fits (ceil(c / 2) boxes of one or two balls), so the loop always returns.

Why it works

The smallest box comes from some number, so k never exceeds the rarest count m. For a fixed k, using fewer than ceil(c / (k + 1)) boxes cannot hold c balls, and using that many works whenever the boxes can be filled to at least k each. Since ceil(c / (k + 1)) only shrinks as k grows, the first feasible k from the top gives the fewest boxes in total.

Complexity

  • Time — O(n + m · d) where d is the number of distinct values
  • Space — O(d)

Pitfalls

  • Box sizes {k, k + 1} must work for all numbers at once — check every count for the same k.
  • Using ceil(c / k) boxes is the wrong count: the larger box size k + 1 gives fewer boxes.
  • Starting k above the rarest count can never succeed.

Reference solution

Python

from typing import List
from collections import Counter

def minGroupsForValidAssignment(balls: List[int]) -> int:
    counts = list(Counter(balls).values())
    m = min(counts)
    for k in range(m, 0, -1):
        total = 0
        ok = True
        for c in counts:
            g = (c + k) // (k + 1)
            if g * k > c:
                ok = False
                break
            total += g
        if ok:
            return total
    return 0

Java

public static int minGroupsForValidAssignment(int[] balls) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int v : balls) freq.merge(v, 1, Integer::sum);
    int m = Integer.MAX_VALUE;
    for (int c : freq.values()) m = Math.min(m, c);
    for (int k = m; k >= 1; k--) {
        int total = 0;
        boolean ok = true;
        for (int c : freq.values()) {
            int g = (c + k) / (k + 1);
            if ((long) g * k > c) { ok = false; break; }
            total += g;
        }
        if (ok) return total;
    }
    return 0;
}

C++

int minGroupsForValidAssignment(vector<int>& balls) {
    unordered_map<int, int> freq;
    for (int v : balls) freq[v]++;
    int m = INT_MAX;
    for (auto& p : freq) m = min(m, p.second);
    for (int k = m; k >= 1; k--) {
        int total = 0;
        bool ok = true;
        for (auto& p : freq) {
            int c = p.second;
            int g = (c + k) / (k + 1);
            if ((long long) g * k > c) { ok = false; break; }
            total += g;
        }
        if (ok) return total;
    }
    return 0;
}

JavaScript

var minGroupsForValidAssignment = function(balls) {
    var freq = new Map();
    for (var i = 0; i < balls.length; i++) freq.set(balls[i], (freq.get(balls[i]) || 0) + 1);
    var counts = Array.from(freq.values());
    var m = balls.length;
    for (var j = 0; j < counts.length; j++) if (counts[j] < m) m = counts[j];
    for (var k = m; k >= 1; k--) {
        var total = 0, ok = true;
        for (var t = 0; t < counts.length; t++) {
            var c = counts[t];
            var g = Math.floor((c + k) / (k + 1));
            if (g * k > c) { ok = false; break; }
            total += g;
        }
        if (ok) return total;
    }
    return 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets