Minimum Number of Groups to Create a Valid Assignment

Minimum Number of Groups to Create a Valid Assignment - 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:

Rule 1: Balls with the same number must be placed in the same box. However, if you have more than one ball with the same number, you can put them in different boxes.

Rule 2: The largest box can only have one more ball than the smallest box (difference ≤ 1).

Return the minimum number of boxes needed to sort these balls following these rules.

Input & Output

Example 1 — Basic Distribution

$ Input: nums = [1,1,2,2,3]

› Output: 3

💡 Note: Frequencies: 1→2, 2→2, 3→1. Need 3 groups with sizes [2,2,1] to satisfy balance constraint (max-min ≤ 1)

Example 2 — All Same Numbers

$ Input: nums = [1,1,1,1]

› Output: 2

💡 Note: All balls have same number, can split into 2 groups of size 2 each: [2,2]

Example 3 — Single Element

$ Input: nums = [5]

› Output: 1

💡 Note: Only one ball, so minimum is 1 group

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 32 M Meta 28 a Amazon 25 MS Microsoft 20

The key insight is to use binary search on the answer space since the problem has a monotonic property - if k groups work, then k+1 groups also work. Count frequencies first, then binary search to find minimum valid group count. Best approach is binary search with Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Group Counts	O(n²)	O(n)	Try every possible number of groups from 1 to n and check validity
Binary Search on Answer Space	O(n log n)	O(n)	Binary search on the number of groups to find minimum valid count

Brute Force - Try All Group Counts — Algorithm Steps

Count frequency of each number in the array
Try each possible number of groups k from 1 to n
For each k, check if valid distribution exists
Return the first k that works

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count how many of each number we have

Try k=1,2,3...

Test each possible number of groups

Check Distribution

See if frequencies fit into k balanced groups

Code -

solution.c — C

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

int canDistribute(int* frequencies, int freqCount, int k, int total) {
    int minSize = total / k;
    int extra = total % k;
    
    int smallGroups = k - extra;
    int largeGroups = extra;
    
    for (int i = 0; i < freqCount; i++) {
        int freq = frequencies[i];
        if (freq > minSize + 1) {
            return 0;
        }
        if (freq == minSize + 1) {
            if (largeGroups > 0) {
                largeGroups--;
            } else {
                return 0;
            }
        } else if (freq == minSize) {
            if (smallGroups > 0) {
                smallGroups--;
            } else if (largeGroups > 0) {
                largeGroups--;
            } else {
                return 0;
            }
        }
    }
    
    return 1;
}

int solution(int* nums, int numsSize) {
    int freq[1001] = {0};
    int maxNum = 0;
    
    for (int i = 0; i < numsSize; i++) {
        freq[nums[i]]++;
        if (nums[i] > maxNum) maxNum = nums[i];
    }
    
    int frequencies[1001];
    int freqCount = 0;
    for (int i = 0; i <= maxNum; i++) {
        if (freq[i] > 0) {
            frequencies[freqCount++] = freq[i];
        }
    }
    
    for (int k = 1; k <= numsSize; k++) {
        if (canDistribute(frequencies, freqCount, k, numsSize)) {
            return k;
        }
    }
    
    return numsSize;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, numsSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n possible group counts, we iterate through all frequencies

⚠ Quadratic Growth

Space Complexity

O(n)

Hash map to store frequency counts

⚡ Linearithmic Space

32.4K Views

Medium Frequency

~25 min Avg. Time

875 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

Brute Force - Try All Group Counts — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler