Maximum Number of Groups Entering a Competition — Solution
Maximum Number of Groups Entering a Competition solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Number of Groups Entering a Competition is a medium coding problem on arrays, math and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Math, Greedy, Binary Search
- 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
grades lists the (positive) grades of the students who want to enter a competition. Every student must be placed in exactly one of a sequence of non-empty groups g_1, g_2, ..., g_k, ordered so that for every i < k:
- the sum of grades in
g_iis strictly less than the sum of grades ing_(i+1), and - the number of students in
g_iis strictly less than the number ing_(i+1).
Return the maximum possible number of groups k.
Example 1
Input: grades = [8,3,5,1,9,4,2]
Output: 3
Explanation: For example `[1]`, `[2,3]`, `[4,5,8,9]`: sizes 1 < 2 < 4 and sums 1 < 5 < 26. Four groups would need at least 1 + 2 + 3 + 4 = 10 students.
Example 2
Input: grades = [6,6]
Output: 1
Explanation: Two groups would need at least 1 + 2 = 3 students.
Example 3
Input: grades = [5]
Output: 1
Constraints
1 <= grades.length <= 10^51 <= grades[i] <= 10^5
Hints for Maximum Number of Groups Entering a Competition
Hint 1
Do the actual grades matter, or only how many students there are?
Hint 2
Sort the grades: if groups take consecutive runs of increasing size from the sorted list, the sums increase automatically.
Hint 3
So the answer is the largest
kwith1 + 2 + ... + k <= n.
How to solve Maximum Number of Groups Entering a Competition
Sizes must strictly increase, so k groups need at least 1 + 2 + ... + k students. That many always suffice, whatever the grades are, so the answer depends on n alone.
Approach
- Let
nbe the number of students. - Find the largest
kwithk(k + 1) / 2 <= n— a loop that keeps taking groups of size 1, 2, 3, ... while enough students remain. - Return
k.
Why it works
Necessity: group sizes are distinct positive integers in increasing order, so the i-th smallest is at least i and the total is at least k(k + 1)/2. Sufficiency: sort the grades ascending and give group i the next i students, putting any leftovers into the last group. Each group has more students than the previous one, and each of them has a grade at least as large as every grade in the previous group, so its sum is strictly larger (grades are positive).
Complexity
- Time —
O(sqrt(n)) - Space —
O(1)
Pitfalls
- No sorting or grade arithmetic is needed in the final algorithm — only the count.
- Leftover students join the last group; they never create a new one.
- Floating-point square roots for
kinvite off-by-one errors; a loop or integer binary search is safer.
Reference solution
Python
from typing import List
def maximumGroups(grades: List[int]) -> int:
n = len(grades)
k = 0
while (k + 1) * (k + 2) // 2 <= n:
k += 1
return kJava
public static int maximumGroups(int[] grades) {
int n = grades.length, k = 0;
while ((long) (k + 1) * (k + 2) / 2 <= n) k++;
return k;
}C++
int maximumGroups(vector<int>& grades) {
long long n = grades.size(), k = 0;
while ((k + 1) * (k + 2) / 2 <= n) k++;
return (int)k;
}JavaScript
var maximumGroups = function(grades) {
var n = grades.length, k = 0;
while ((k + 1) * (k + 2) / 2 <= n) k++;
return k;
};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 · Greedy Algorithms