Maximum Number of Groups With Increasing Length - Solution & Explanation
Problem Statement
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.
This C solution first sorts the usageLimits using quicksort. It then iterates through the array and checks if each number can satisfy the current required group size. If it can, a new group is formed, and the required group size is incremented. This process continues until the numbers can't satisfy the current group size.
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as the operation is done in-place.
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.
This C implementation uses binary search to find the maximum number of groups that can be formed. It checks whether a specified number of groups can be formed using a helper function canFormGroups which verifies if a given number of groups is feasible under the given constraints. Specific potential group numbers are tested through binary search until the optimal count is found.
Complexity
Time Complexity: O(n log n) for sorting and binary search operations.
Space Complexity: O(1) additional storage used.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
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 operations. |
| Default Approach | — |
Detailed 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. |
Video Solution
Leetcode Weekly contest 355 - Hard - Maximum Number of Groups With Increasing Length • Prakhar Agrawal • 2,213 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Maximum Number of Groups With Increasing Length easy or hard?
Maximum Number of Groups With Increasing Length Python/Java solution
How to solve Maximum Number of Groups With Increasing Length in O(n)?
What is the best approach for Maximum Number of Groups With Increasing Length?
Is Maximum Number of Groups With Increasing Length asked at Google/Amazon/Meta?
What data structure is used in Maximum Number of Groups With Increasing Length?
What is the time complexity of Maximum Number of Groups With Increasing Length?
Ready to solve this problem?
Practice Maximum Number of Groups With Increasing Length with our built-in code editor and test cases.
Practice on FleetCode