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:
ith group is less than the sum of the grades of students in the (i + 1)th group, for all groups (except the last).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 <= 1051 <= grades[i] <= 105Problem 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.
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.
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.
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.
JavaScript
Java
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.
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.
| Approach | Complexity |
|---|---|
| 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 | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Greedy | O(n log n) | O(1) | When working directly with the grades array and reasoning about group formation step by step |
| Mathematical Incremental Grouping | O(1) | O(1) | Optimal solution when you recognize the triangular number pattern |
| Binary Search on Group Count | O(log n) | O(1) | Useful when converting the constraint k(k+1)/2 ≤ n into a monotonic search problem |
2358. Maximum Number of Groups Entering a Competition || Leetcode Weekly Contest 304 • Bro Coders • 3,086 views views
Watch 9 more video solutions →Practice Maximum Number of Groups Entering a Competition with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor