Maximum Number of Groups With Increasing Length

Hard
895.

Maximum Number of Groups With Increasing Length

Maximum Number of Groups With Increasing Length is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Rubrik interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} usageLimits
 * @return {number}
 */
var maxIncreasingGroups = function(usageLimits) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Number of Groups With Increasing Length — Solution

Maximum Number of Groups With Increasing Length solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Number of Groups With Increasing Length is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Rubrik interviews.

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

Hints for Maximum Number of Groups With Increasing Length

  1. Hint 1

    With k groups the sizes must be at least 1, 2, …, k, needing k(k+1)/2 usages in total.

  2. Hint 2

    That count is also sufficient, provided you have enough distinct numbers — and sorting ascending makes the check greedy.

  3. Hint 3

    Sweep the sorted limits, and whenever the running total reaches the next triangular number, one more group fits.

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

  1. Sort usageLimits ascending.
  2. Keep a running total and a group count k.
  3. After adding each limit, if the total reaches (k+1)(k+2)/2, increment k.
  4. 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

Java

public static int maxIncreasingGroups(int[] usageLimits) {
    int[] a = usageLimits.clone();
    Arrays.sort(a);
    long total = 0;
    long k = 0;
    for (int v : a) {
        total += v;
        if (total >= (k + 1) * (k + 2) / 2) k++;
    }
    return (int) k;
}

C++

int maxIncreasingGroups(vector<int>& usageLimits) {
    vector<int> a = usageLimits;
    sort(a.begin(), a.end());
    long long total = 0, k = 0;
    for (int v : a) {
        total += v;
        if (total >= (k + 1) * (k + 2) / 2) k++;
    }
    return (int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms