Maximum Number of Groups With Increasing Length solution and explanation
7 more videos on this problem
Leetcode Weekly contest 355 - Hard - Maximum Number of Groups With Increasing LengthPrakhar Agrawal · 15:09 · 2K views
2790. Maximum Number of Groups With Increasing Length || Weekly Contest 355 || Leetcode || HindiAshish Kumar · 16:07 · 1K views
2790. Maximum Number of Groups With Increasing Length (Leetcode Hard)Programming Live with Larry · 27:43 · 1K views
Maximum Number of Groups With Increasing Length | Leetcode 2790 | Greedy | Contest 355Tech Courses · 13:13 · 1K views
2790. Maximum Number of Groups With Increasing Length | Leetcode Hardquebeat · 19:58 · 634 views
Cracking LeetCode 2790. Maximum Number of Groups With Increasing Length Every Step Explained PythonvanAmsen · 7:35 · 506 views
[Eng] Leetcode Weekly Contest 355 | 2790. Maximum Number of Groups With Increasing LengthCyCode · 22:30 · 419 views
Leetcode Hard || 2790. Maximum Number of Groups With Increasing Length || Weekly Contest 355CORROSIVE · 17:32 · 292 views
The problem
You are given a 0-indexed array usageLimits of length n.
Your task is to create groups using numbers from 0 to n - 1, ensuring that each number, i, is used no more than usageLimits[i] times in total across all groups. You must also satisfy the following conditions:
- Each group must consist of distinct numbers, meaning that no duplicate numbers are allowed within a single group.
- Each group (except the first one) must have a length strictly greater than the previous group.
Return an integer denoting the maximum number of groups you can create while satisfying these conditions.
Example 1:
Input: usageLimits = [1,2,5]
Output: 3
Explanation: In this example, we can use 0 at most once, 1 at most twice, and 2 at most five times.
One way of creating the maximum number of groups while satisfying the conditions is:
Group 1 contains the number [2].
Group 2 contains the numbers [1,2].
Group 3 contains the numbers [0,1,2].
It can be shown that the maximum number of groups is 3.
So, the output is 3.
Example 2:
Input: usageLimits = [2,1,2]
Output: 2
Explanation: In this example, we can use 0 at most twice, 1 at most once, and 2 at most twice.
One way of creating the maximum number of groups while satisfying the conditions is:
Group 1 contains the number [0].
Group 2 contains the numbers [1,2].
It can be shown that the maximum number of groups is 2.
So, the output is 2.
Example 3:
Input: usageLimits = [1,1]
Output: 1
Explanation: In this example, we can use both 0 and 1 at most once.
One way of creating the maximum number of groups while satisfying the conditions is:
Group 1 contains the number [0].
It can be shown that the maximum number of groups is 1.
So, the output is 1.
Constraints:
1 <= usageLimits.length <= 1051 <= usageLimits[i] <= 109
Approach overview
Problem Overview: You receive an array usageLimits where usageLimits[i] represents how many times number i can be used. Build groups whose sizes strictly increase (1, 2, 3, ...). Each group must contain distinct numbers, and every number cannot be used more than its allowed limit. The task is to compute the maximum number of such groups you can form.
Approach 1: Greedy Approach Using Sorting (O(n log n) time, O(1) extra space)
Sort usageLimits first. This allows you to process numbers with smaller capacities early while accumulating the total number of times elements can be used. Maintain a running sum of all limits seen so far. If the accumulated usage is enough to support the total size required for k + 1 groups (which is (k+1)(k+2)/2 elements overall), you can safely form another group. The key insight is that group order does not matter once capacities are pooled together. Sorting ensures the greedy accumulation never wastes smaller limits early. This solution works well because you only track total available capacity rather than explicitly constructing groups. Relevant topics include Greedy, Sorting, and Array.
Approach 2: Binary Search on Number of Groups (O(n log n) time, O(1) space)
Instead of building groups incrementally, search for the largest possible k. For a candidate value k, check whether forming k groups is feasible. Across k groups, each number can appear at most once per group, meaning each number contributes at most min(usageLimits[i], k) total usages. Sum these contributions and verify whether the total is at least k(k+1)/2, which is the number of elements required to build groups of sizes 1..k. Binary search over k from 0 to n, using this feasibility check to narrow the answer. This approach highlights the mathematical structure of the requirement and demonstrates the use of Binary Search with a monotonic condition.
Recommended for interviews: The greedy sorting approach is typically expected. It shows you recognize that only the total capacity matters once limits are aggregated. Starting with the binary search formulation demonstrates strong reasoning about constraints and feasibility checks, but the greedy accumulation is simpler and more elegant once you spot the pattern.
Approach 1: Greedy Approach Using Sorting
In this approach, the array usageLimits is first sorted. This allows us to start forming groups from the smallest usage limits, which can facilitate forming more groups. We begin constructing groups of increasing size, taking advantage of the sorted order. Each time we try to form a group, we ensure the previous groups are fully satisfied with the distinctness condition. If the current group size exceeds the allowed usage of a number, the next number in line must be used to satisfy the condition.
def maxNumberOfGroups(usageLimits):
usageLimits.sort()
groups = 0
next_group_size = 1
for limit in usageLimits:
if limit >= next_group_size:
groups += 1
next_group_size += 1
return groups
if __name__ == "__main__":
usageLimits = [1, 2, 5]
print(maxNumberOfGroups(usageLimits))import java.util.Arrays;
public class Solution {
public int maxNumberOfGroups(int[] usageLimits) {
Arrays.sort(usageLimits);
int groups = 0;
int nextGroupSize = 1;
for (int limit : usageLimits) {
if (limit >= nextGroupSize) {
groups++;
nextGroupSize++;
}
}
return groups;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] usageLimits = {1, 2, 5};
System.out.println(solution.maxNumberOfGroups(usageLimits));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int maxNumberOfGroups(std::vector<int>& usageLimits) {
std::sort(usageLimits.begin(), usageLimits.end());
int groups = 0;
int nextGroupSize = 1;
for (int limit : usageLimits) {
if (limit >= nextGroupSize) {
groups++;
nextGroupSize++;
}
}
return groups;
}
int main() {
std::vector<int> usageLimits = {1, 2, 5};
std::cout << maxNumberOfGroups(usageLimits) << std::endl;
return 0;
}function maxNumberOfGroups(usageLimits) {
usageLimits.sort((a, b) => a - b);
let groups = 0;
let nextGroupSize = 1;
for (let limit of usageLimits) {
if (limit >= nextGroupSize) {
groups++;
nextGroupSize++;
}
}
return groups;
}
console.log(maxNumberOfGroups([1, 2, 5]));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*) a - *(int*) b);
}
int maxNumberOfGroups(int* usageLimits, int usageLimitsSize) {
qsort(usageLimits, usageLimitsSize, sizeof(int), compare);
int groups = 0;
int nextGroupSize = 1;
for (int i = 0; i < usageLimitsSize; i++) {
if (usageLimits[i] >= nextGroupSize) {
groups++;
nextGroupSize++;
}
}
return groups;
}
int main() {
int usageLimits[] = {1, 2, 5};
int n = sizeof(usageLimits) / sizeof(usageLimits[0]);
printf("%d\n", maxNumberOfGroups(usageLimits, n));
return 0;
}using System;
using System.Linq;
public class Solution {
public int MaxNumberOfGroups(int[] usageLimits) {
Array.Sort(usageLimits);
int groups = 0;
int nextGroupSize = 1;
foreach (int limit in usageLimits) {
if (limit >= nextGroupSize) {
groups++;
nextGroupSize++;
}
}
return groups;
}
public static void Main(string[] args) {
int[] usageLimits = { 1, 2, 5 };
var solution = new Solution();
Console.WriteLine(solution.MaxNumberOfGroups(usageLimits));
}
}In Python, we use the sort method to organize the usage limits. The algorithm iterates through these, constructing as many groups as possible by checking each limit against the needed group size. This greedy strategy optimizes the use of available numbers.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) additional memory usage.
Approach 2: Binary Search Approach
This approach involves using binary search to find the maximum number of groups that can be formed. The key insight here is to utilize binary search to determine the largest possible number that can be used as the group size. We start by sorting the usage limits and use a binary search on the potential number of groups from 1 to n, checking each possibility by consuming limits accordingly.
def can_form_groups(usageLimits, groups):
total = sum(min(limit, groups) for limit in usageLimits)
return total >= groups * (groups + 1) // 2
def max_number_of_groups(usageLimits):
usageLimits.sort()
left, right = 1, len(usageLimits)
while left < right:
mid = left + (right - left + 1) // 2
if can_form_groups(usageLimits, mid):
left = mid
else:
right = mid - 1
return left
if __name__ == "__main__":
usageLimits = [1, 2, 5]
print(max_number_of_groups(usageLimits))import java.util.Arrays;
public class Solution {
private boolean canFormGroups(int[] usageLimits, int groups) {
long sum = 0;
for (int limit : usageLimits) {
sum += Math.min(limit, groups);
}
return sum >= (long) groups * (groups + 1) / 2;
}
public int maxNumberOfGroups(int[] usageLimits) {
Arrays.sort(usageLimits);
int left = 1, right = usageLimits.length;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (canFormGroups(usageLimits, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] usageLimits = {1, 2, 5};
System.out.println(solution.maxNumberOfGroups(usageLimits));
}
}#include <iostream>
#include <vector>
#include <algorithm>
bool canFormGroups(const std::vector<int>& usageLimits, int groups) {
long long sum = 0;
for (int limit : usageLimits) {
sum += std::min(limit, groups);
}
return sum >= (long long) groups * (groups + 1) / 2;
}
int maxNumberOfGroups(std::vector<int>& usageLimits) {
std::sort(usageLimits.begin(), usageLimits.end());
int left = 1, right = usageLimits.size();
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (canFormGroups(usageLimits, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
int main() {
std::vector<int> usageLimits = {1, 2, 5};
std::cout << maxNumberOfGroups(usageLimits) << std::endl;
return 0;
}function canFormGroups(usageLimits, groups) {
let total = 0;
for (let limit of usageLimits) {
total += Math.min(limit, groups);
}
return total >= groups * (groups + 1) / 2;
}
function maxNumberOfGroups(usageLimits) {
usageLimits.sort((a, b) => a - b);
let left = 1, right = usageLimits.length;
while (left < right) {
let mid = left + ((right - left + 1) >> 1);
if (canFormGroups(usageLimits, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
console.log(maxNumberOfGroups([1, 2, 5]));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*) a - *(int*) b);
}
int canFormGroups(int* usageLimits, int usageLimitsSize, int groups) {
long long sum = 0;
for (int i = 0; i < usageLimitsSize; ++i) {
if (usageLimits[i] >= groups) {
sum += groups;
} else {
sum += usageLimits[i];
}
}
return sum >= (long long) groups * (groups + 1) / 2;
}
int maxNumberOfGroups(int* usageLimits, int usageLimitsSize) {
qsort(usageLimits, usageLimitsSize, sizeof(int), compare);
int left = 1, right = usageLimitsSize;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (canFormGroups(usageLimits, usageLimitsSize, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
int main() {
int usageLimits[] = {1, 2, 5};
int n = sizeof(usageLimits) / sizeof(usageLimits[0]);
printf("%d\n", maxNumberOfGroups(usageLimits, n));
return 0;
}using System;
using System.Linq;
public class Solution {
private bool CanFormGroups(int[] usageLimits, int groups) {
long total = 0;
foreach (int limit in usageLimits) {
total += Math.Min(limit, groups);
}
return total >= (long) groups * (groups + 1) / 2;
}
public int MaxNumberOfGroups(int[] usageLimits) {
Array.Sort(usageLimits);
int left = 1, right = usageLimits.Length;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (CanFormGroups(usageLimits, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
public static void Main(string[] args) {
int[] usageLimits = { 1, 2, 5 };
var solution = new Solution();
Console.WriteLine(solution.MaxNumberOfGroups(usageLimits));
}
}In this Python implementation, binary search helps in determining the maximum number of groups. With a helper function, each number of groups' feasibility is checked via sum calculation, providing optimal results while adhering to input constraints.
Time Complexity: O(n log n) for sorting and binary search.
Space Complexity: O(1) beyond input space.
Approach 3: Default Approach
function maxIncreasingGroups(usageLimits: number[]): number {
usageLimits.sort((a, b) => a - b);
let k = 0;
let s = 0;
for (const x of usageLimits) {
s += x;
if (s > k) {
++k;
s -= k;
}
}
return k;
}func maxIncreasingGroups(usageLimits []int) int {
sort.Ints(usageLimits)
s, k := 0, 0
for _, x := range usageLimits {
s += x
if s > k {
k++
s -= k
}
}
return k
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach Using Sorting | Time Complexity: O(n log n) due to sorting. |
| Binary Search Approach | Time Complexity: O(n log n) for sorting and binary search. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Approach Using Sorting | O(n log n) | O(1) | Best general solution. Simple logic after sorting and commonly expected in interviews. |
| Binary Search on Number of Groups | O(n log n) | O(1) | Useful when reasoning about feasibility checks or demonstrating binary search on answer space. |
Frequently asked questions
Is Maximum Number of Groups With Increasing Length easy or hard?
LeetCode classifies this problem as Hard because the greedy insight is not immediately obvious. The challenge is realizing that total usage capacity determines whether increasing group sizes are feasible, rather than explicitly constructing the groups.
Maximum Number of Groups With Increasing Length Python/Java solution
Implementations typically sort the usageLimits array, maintain a cumulative sum, and increase the group count whenever the total capacity reaches the required threshold. The same greedy logic works across Python, Java, C++, C#, and JavaScript with identical O(n log n) complexity.
How to solve Maximum Number of Groups With Increasing Length in O(n)?
A strict O(n) solution is difficult because most implementations sort the limits first. After sorting, a linear greedy scan determines how many groups can be formed by checking whether the accumulated usage is at least k(k+1)/2 for k groups.
What is the best approach for Maximum Number of Groups With Increasing Length?
The greedy sorting approach is the most practical solution. Sort the usage limits, accumulate the total available usages, and form a new group whenever the accumulated capacity can cover the required elements for the next group. This runs in O(n log n) time due to sorting and uses O(1) extra space.
Is Maximum Number of Groups With Increasing Length asked at Google/Amazon/Meta?
Problems involving greedy grouping, resource allocation, and binary search on the answer frequently appear in interviews at companies like Google, Amazon, and Meta. This question tests reasoning about capacity constraints and mathematical feasibility conditions.
What data structure is used in Maximum Number of Groups With Increasing Length?
The main structure is an array representing usage limits. The solution relies on sorting the array and maintaining a running sum. No advanced data structures are required, but concepts from greedy algorithms, math, and binary search are key.
What is the time complexity of Maximum Number of Groups With Increasing Length?
The optimal solutions run in O(n log n) time. The greedy approach spends O(n log n) time sorting the array and then performs a linear scan. The binary search method also ends up around O(n log n) because each feasibility check is O(n) and it runs for O(log n) iterations.