Maximum Number of Groups Entering a Competition

Medium
1157.

Maximum Number of Groups Entering a Competition

Maximum Number of Groups Entering a Competition is a medium coding problem on arrays, math and greedy, asked in Amazon and Google interviews.

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_i is strictly less than the sum of grades in g_(i+1), and
  • the number of students in g_i is strictly less than the number in g_(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^5
  • 1 <= grades[i] <= 10^5
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[]} grades
 * @return {number}
 */
var maximumGroups = function(grades) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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_i is strictly less than the sum of grades in g_(i+1), and
  • the number of students in g_i is strictly less than the number in g_(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^5
  • 1 <= grades[i] <= 10^5

Hints for Maximum Number of Groups Entering a Competition

  1. Hint 1

    Do the actual grades matter, or only how many students there are?

  2. Hint 2

    Sort the grades: if groups take consecutive runs of increasing size from the sorted list, the sums increase automatically.

  3. Hint 3

    So the answer is the largest k with 1 + 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

  1. Let n be the number of students.
  2. Find the largest k with k(k + 1) / 2 <= n — a loop that keeps taking groups of size 1, 2, 3, ... while enough students remain.
  3. 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 k invite 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 k

Java

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