Skip to main content
Talentd

Maximum Number of Groups Entering a Competition - Solution & Explanation

MediumArrayMathBinary SearchGreedy14 min read
Practice this problem

Problem Statement

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.

 

Example 1:

Input: grades = [10,6,12,7,3,5]
Output: 3
Explanation: The following is a possible way to form 3 groups of students:
- 1st group has the students with grades = [12]. Sum of grades: 12. Student count: 1
- 2nd group has the students with grades = [6,7]. Sum of grades: 6 + 7 = 13. Student count: 2
- 3rd group has the students with grades = [10,3,5]. Sum of grades: 10 + 3 + 5 = 18. Student count: 3
It can be shown that it is not possible to form more than 3 groups.

Example 2:

Input: grades = [8,8]
Output: 1
Explanation: We can only form 1 group, since forming 2 groups would lead to an equal number of students in both groups.

 

Constraints:

  • 1 <= grades.length <= 105
  • 1 <= grades[i] <= 105

Approach Overview

Problem Overview: You receive an array grades representing student scores. Students must be divided into groups such that each new group has more members than the previous one and the total grade sum is strictly larger than the previous group. The task is to compute the maximum number of groups you can form.

Approach 1: Sorting and Greedy Approach (O(n log n) time, O(1) extra space)

Sort the array so smaller grades appear first. Greedy grouping works because building groups with the smallest available elements keeps early sums minimal, leaving larger elements for later groups. Iterate through the sorted list while expanding the next group size from 1, 2, 3.... Maintain counters for the current group size and the total number of used students. Each time you have enough remaining students to form the next larger group, commit that group and move forward. Sorting guarantees that each later group naturally has a larger sum because it contains more elements and larger values. This approach uses a classic greedy strategy combined with an array traversal.

Approach 2: Mathematical Incremental Grouping (O(1) time, O(1) space)

The key observation: if group sizes are strictly increasing, they must follow 1, 2, 3, ..., k. The total number of students required is the triangular number 1 + 2 + ... + k = k(k+1)/2. Because grades are positive and the array can be sorted, satisfying the size condition automatically ensures the sum condition. Therefore the task reduces to finding the largest k such that k(k+1)/2 ≤ n, where n is the number of students. Solve this using the quadratic formula or a small iterative check. This turns the problem into a simple math calculation.

Alternative: Binary Search on Group Count (O(log n) time, O(1) space)

You can also treat the number of groups k as the search space. Using binary search, check whether k(k+1)/2 ≤ n. If the condition holds, try a larger k; otherwise reduce it. This approach is useful when the formula is not immediately obvious or when interviewers want to see how you convert a monotonic condition into a search problem.

Recommended for interviews: The mathematical observation is the cleanest and runs in constant time. However, many candidates first discover the greedy grouping after sorting, which demonstrates clear reasoning about constraints. Showing the greedy idea and then simplifying it to the triangular-number formula signals strong problem-solving ability.

Approach 1: Sorting and Greedy Approach

This approach involves sorting the grades array first. After sorting, we can use a greedy strategy to split the students into groups ensuring both conditions mentioned in the question are met. We incrementally build each group by satisfying both the conditions of increasing sum and increasing count.

Python Solution: The solution sorts the grades array first. For each student grade, we try to add it to the current group, and check if the total count and sum conditions are satisfied. If they are, we finalize that group, reset the sums, and increment the group count.

Code

PythonC

Python

C

Complexity

Time Complexity: O(n log n) due to the sorting step, followed by O(n) for the greedy iteration. Space Complexity: O(1) as we use a few extra variables without additional data structures.

Try this approach in the editor →

Approach 2: Mathematical Incremental Grouping

This approach takes advantage of the mathematical observation that if we progressively try to build larger groups (i.e., first group of 1, second of 2, etc.), we can check if the total students are enough to fulfill this pattern.

JavaScript Solution: This method involves sorting and using a mathematical formula to determine the maximum number of groups by checking if the candidate group number fits within the sum constraints.

Code

JavaScriptJava

JavaScript

Java

Complexity

Time Complexity: O(n log n) for sorting, O(n) for validation. Space Complexity: O(1), only a few variables used for storing intermediate results.

Try this approach in the editor →

Approach 3: Greedy + Binary Search

Observing the conditions in the problem, the number of students in the i-th group must be less than that in the (i+1)-th group, and the total score of students in the i-th group must be less than that in the (i+1)-th group. We only need to sort the students by their scores in ascending order, and then assign 1, 2, ..., k students to each group in order. If the last group does not have enough students for k, we can distribute these students to the previous last group.

Therefore, we need to find the largest k such that \frac{(1 + k) times k}{2} leq n, where n is the total number of students. We can use binary search to solve this.

We define the left boundary of binary search as l = 1 and the right boundary as r = n. Each time, the midpoint is mid = \lfloor \frac{l + r + 1}{2} \rfloor. If (1 + mid) times mid \gt 2 times n, it means mid is too large, so we shrink the right boundary to mid - 1; otherwise, we increase the left boundary to mid.

Finally, we return l as the answer.

The time complexity is O(log n) and the space complexity is O(1), where n is the total number of students.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting and Greedy Approach

Time Complexity: O(n log n) due to the sorting step, followed by O(n) for the greedy iteration. Space Complexity: O(1) as we use a few extra variables without additional data structures.

Mathematical Incremental Grouping

Time Complexity: O(n log n) for sorting, O(n) for validation. Space Complexity: O(1), only a few variables used for storing intermediate results.

Greedy + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and GreedyO(n log n)O(1)When working directly with the grades array and reasoning about group formation step by step
Mathematical Incremental GroupingO(1)O(1)Optimal solution when you recognize the triangular number pattern
Binary Search on Group CountO(log n)O(1)Useful when converting the constraint k(k+1)/2 ≤ n into a monotonic search problem

Video Solution

2358. Maximum Number of Groups Entering a Competition || Leetcode Weekly Contest 304 • Bro Coders • 3,101 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Number of Groups Entering a Competition easy or hard?
The problem is rated Medium because the greedy approach is straightforward but recognizing the triangular-number pattern requires mathematical insight. Once that observation is made, the implementation becomes extremely short.
Maximum Number of Groups Entering a Competition Python/Java solution
In Python or Java, the cleanest implementation computes k from the inequality k(k+1)/2 ≤ n. This can be derived using the quadratic formula with sqrt(8n+1). Alternatively, sort the array and greedily form groups with sizes 1, 2, 3 until you run out of students.
How to solve Maximum Number of Groups Entering a Competition in O(n)?
You do not actually need O(n) processing because the optimal solution depends only on the number of students. Compute the largest k where k(k+1)/2 ≤ n using the quadratic formula or a small loop. This effectively reduces the problem to constant time instead of iterating through the array.
What is the best approach for Maximum Number of Groups Entering a Competition?
The optimal approach uses a mathematical observation. If groups must have increasing sizes, they follow 1, 2, 3, ..., k. The total students required is k(k+1)/2. The largest k satisfying k(k+1)/2 ≤ n (where n is the number of students) is the answer, which can be computed in O(1) time.
Is Maximum Number of Groups Entering a Competition asked at Google/Amazon/Meta?
Problems combining greedy reasoning with mathematical patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variations involving triangular numbers, grouping constraints, or greedy selection are common in mid‑level coding rounds.
What data structure is used in Maximum Number of Groups Entering a Competition?
The problem mainly uses arrays and simple counters. In the greedy solution, the grades array is sorted and iterated through. The optimal mathematical solution does not require additional data structures beyond basic arithmetic variables.
What is the time complexity of Maximum Number of Groups Entering a Competition?
The optimal mathematical solution runs in O(1) time and O(1) space. A more intuitive greedy approach sorts the grades array and forms groups incrementally, which takes O(n log n) time due to sorting and constant extra space.

Ready to solve this problem?

Practice Maximum Number of Groups Entering a Competition with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Height by Stacking Cuboids