Scale Engineer

Maximum Number of Groups Entering a Competition

Med
#2147Time: O(n log n), dominated by the sorting of the `grades` array. The subsequent loop runs `O(sqrt(n))` times, which is less significant.Space: O(log n) or O(n), depending on the space used by the sorting algorithm's implementation (e.g., for recursion stack or temporary arrays).
Patterns
MathGreedy
Algorithms
Binary Search
Data structures
Array

Prompt

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

Approaches

4 approaches with complexity analysis and trade-offs.

This approach is based on the intuition that to satisfy the sum condition (sum_i < sum_{i+1}), we should assign students with lower grades to earlier groups and students with higher grades to later groups. By sorting the grades array first, we can guarantee that if we form groups with increasing sizes (count_i < count_{i+1}), the sum condition will also be met. After sorting, we can greedily determine the number of groups.

Algorithm

  • Get the total number of students, n, from the length of the grades array.
  • Sort the grades array in non-decreasing order. This step ensures that if we form groups with increasing sizes, the sum of grades will also be strictly increasing.
  • Initialize k = 0 (number of groups) and studentsUsed = 0.
  • Iterate with nextGroupSize starting from 1.
  • In each step, check if we have enough remaining students to form a group of this size, i.e., if studentsUsed + nextGroupSize <= n.
  • If we do, it means we can form another group. Increment k, add nextGroupSize to studentsUsed, and increment nextGroupSize for the next iteration.
  • If not, we don't have enough students, so we stop.
  • Return k as the maximum number of groups.

Walkthrough

The core idea is that if we sort the grades in non-decreasing order, any group formed from consecutive students will have a smaller sum than the next group of a larger size formed from the subsequent students. This is because the later group will have more students, and each of its students will have a grade greater than or equal to any student in the previous group.

The algorithm proceeds as follows:

  1. Sort the grades array.
  2. Greedily form groups of increasing size: 1, 2, 3, and so on.
  3. We keep track of the number of students used. We start by forming a group of size 1, then size 2, and so on, as long as we have enough students remaining.
  4. The total number of groups we can form this way is the maximum possible.

The sorting step is the bottleneck, making this approach less efficient than others that realize the grade values are irrelevant.

import java.util.Arrays; class Solution {    public int maximumGroups(int[] grades) {        int n = grades.length;        // Sorting is done to satisfy the sum condition easily, but as we'll see        // in other approaches, it's not strictly necessary to solve the problem.        Arrays.sort(grades);                int k = 0; // number of groups        int studentsUsed = 0;        int nextGroupSize = 1;                while (studentsUsed + nextGroupSize <= n) {            studentsUsed += nextGroupSize;            k++;            nextGroupSize++;        }                return k;    }}

Complexity

Time

O(n log n), dominated by the sorting of the `grades` array. The subsequent loop runs `O(sqrt(n))` times, which is less significant.

Space

O(log n) or O(n), depending on the space used by the sorting algorithm's implementation (e.g., for recursion stack or temporary arrays).

Trade-offs

Pros

  • Conceptually simple and directly models the problem constraints after sorting.

  • Guaranteed to be correct.

Cons

  • Highly inefficient due to the unnecessary sorting step, which has a time complexity of O(n log n).

  • The core logic of the problem does not depend on the actual grade values, making the sorting redundant.

Solutions

class Solution {public  int maximumGroups(int[] grades) {    int n = grades.length;    int l = 0, r = n;    while (l < r) {      int mid = (l + r + 1) >> 1;      if (1L * mid * mid + mid > n * 2L) {        r = mid - 1;      } else {        l = mid;      }    }    return l;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem