Maximum Number of Groups With Increasing Length — Hard Problem & Solution

You have numbers 0 … n-1, and number i may be used at most usageLimits[i] times in total.

Difficulty: Hard
Topics: Arrays, Greedy, Sorting, Binary Search
Asked at: Amazon, Google, Rubrik
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You have numbers 0 … n-1, and number i may be used at most usageLimits[i] times in total.

Build groups so that each group holds distinct numbers and every group after the first is strictly longer than the one before. Return the maximum number of groups.

Example 1

Input: usageLimits = [1,2,5]
Output: 3
Explanation: Groups of sizes 1, 2 and 3.

Example 2

Input: usageLimits = [2,1,2]
Output: 2
Explanation: Sizes 1 and 2; a third group of size 3 needs 6 usages but only 5 exist.

Example 3

Input: usageLimits = [1,1]
Output: 1

Constraints

1 <= usageLimits.length <= 100000
1 <= usageLimits[i] <= 1000000000

How to solve Maximum Number of Groups With Increasing Length

Sort the limits ascending and sweep. After consuming the i smallest limits, the total usages available is their sum; k groups are achievable exactly when that sum reaches k(k+1)/2 while at least k numbers have been consumed — and sorting makes both conditions line up.

Approach

Sort usageLimits ascending.
Keep a running total and a group count k.
After adding each limit, if the total reaches (k+1)(k+2)/2, increment k.
Return k.

Why it works

The necessity is clear: k groups need at least 1 + 2 + … + k usages and at least k distinct numbers (the largest group needs k of them). Sufficiency follows from the sorted sweep: processing the smallest limits first means that by the time the total reaches the k-th triangular number, at least k numbers have contributed — so a valid assignment exists, filling the largest group from the most plentiful numbers.

Complexity

Time — O(n log n)
Space — O(n)

Pitfalls

The running total reaches about 10^14, so it needs 64-bit.
(k+1)(k+2)/2 also exceeds 32 bits for large k — compute it in 64-bit.
Sorting descending breaks the argument; the smallest limits must come first.

Reference solution

Python

from typing import List

def maxIncreasingGroups(usageLimits: List[int]) -> int:
    a = sorted(usageLimits)
    total = k = 0
    for v in a:
        total += v
        if total >= (k + 1) * (k + 2) // 2:
            k += 1
    return k

JavaScript

var maxIncreasingGroups = function(usageLimits) {
    var a = usageLimits.slice().sort(function(x, y) { return x - y; });
    var total = 0, k = 0;
    for (var i = 0; i < a.length; i++) {
        total += a[i];
        if (total >= (k + 1) * (k + 2) / 2) k++;
    }
    return k;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue