Maximum Number of Groups Entering a Competition

Maximum Number of Groups Entering a Competition - Problem

You are given a positive integer array grades which represents the grades of students in a university. You would like to enter all these students into a competition in ordered non-empty groups, such that the ordering meets the following conditions:

The sum of the grades of students in the ith group is less than the sum of the grades of students in the (i + 1)th group, for all groups (except the last).
The total number of students in the ith group is less than the total number of students in the (i + 1)th group, for all groups (except the last).

Return the maximum number of groups that can be formed.

Input & Output

Example 1 — Basic Case

$ Input: grades = [10,6,12,7,3,5]

› Output: 3

💡 Note: Sort to get [3,5,6,7,10,12]. Form groups: [3] (sum=3), [5,6] (sum=11), [7,10,12] (sum=29). Constraints satisfied: 3 < 11 < 29 (sums) and 1 < 2 < 3 (sizes).

Example 2 — Small Array

$ Input: grades = [8,8]

› Output: 1

💡 Note: With only 2 students, we can only form 1 group containing both students. Cannot form 2 groups because that would require the second group to have more students than the first.

Example 3 — Edge Case

$ Input: grades = [1,2,3,4,5,6]

› Output: 3

💡 Note: Already sorted. Optimal grouping: [1] (sum=1), [2,3] (sum=5), [4,5,6] (sum=15). Cannot form 4 groups because we'd need groups of sizes 1,2,3,4 but only have 6 students total.

Constraints

1 ≤ grades.length ≤ 10⁵
1 ≤ grades[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array of student grades: [10,6,12,7,3,5]

Sort & Group

Sort grades and form groups: [3] | [5,6] | [7,10,12]

Verify

Check constraints: sums 3<11<29, sizes 1<2<3

Key Takeaway

🎯 Key Insight: Sort grades and greedily form groups using smallest available elements to maximize the total number of groups

Asked in

G Google 25 a Amazon 20 M Microsoft 15 Apple 12

The key insight is that sorting the grades and using a greedy approach works optimally. By forming groups with consecutive smallest available grades, we maximize the number of groups possible. The greedy approach is most efficient with time complexity O(n log n) and space O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(n² log n)	O(1)	Binary search on the number of groups, check if k groups can be formed
Brute Force - Try All Partitions	O(2^n × n)	O(n)	Generate all possible ways to partition students into groups and check constraints
Greedy Approach	O(n log n)	O(1)	Sort grades and greedily form smallest possible groups

Binary Search on Answer — Algorithm Steps

Binary search on answer from 1 to n groups
For each k, check if k groups can be formed using greedy assignment
Return the largest feasible k

Visualization

Tap to expand

Step-by-Step Walkthrough

Search Space

Binary search from 1 to n groups

Validation

For each mid, check if mid groups can be formed

Narrow Range

Update search range based on validation result

Code -

solution.c — C

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

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

bool canFormKGroups(int* grades, int n, int k) {
    if (k == 1) return true;
    
    int used = 0;
    int prevSum = 0;
    
    for (int groupNum = 1; groupNum <= k; groupNum++) {
        int groupSize = groupNum;
        
        if (used + groupSize > n) {
            return false;
        }
        
        // Calculate sum of next groupSize elements
        int currentSum = 0;
        for (int i = used; i < used + groupSize; i++) {
            currentSum += grades[i];
        }
        
        // Check if sum constraint is satisfied
        if (groupNum > 1 && currentSum <= prevSum) {
            return false;
        }
        
        prevSum = currentSum;
        used += groupSize;
    }
    
    return true;
}

int solution(int* grades, int gradesSize) {
    qsort(grades, gradesSize, sizeof(int), compare);
    
    // Binary search on answer
    int left = 1, right = gradesSize;
    int answer = 1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (canFormKGroups(grades, gradesSize, mid)) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return answer;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse array manually
    int grades[100];
    int size = 0;
    char* token = strtok(line + 1, ",]"); // Skip '['
    while (token != NULL) {
        grades[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(grades, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² log n)

O(log n) binary search iterations, each taking O(n²) to validate in worst case

⚠ Quadratic Growth

Space Complexity

O(1)

Only constant extra space for binary search variables

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 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

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler