Watch 9 video solutions for Maximum Number of Groups With Increasing Length, a hard level problem involving Array, Math, Binary Search. This walkthrough by Prakhar Agrawal has 2,210 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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] <= 109Problem 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 | 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. |