Maximum Number of Groups With Increasing Length — LeetCode 2790 Python Solution

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.

Example

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.

Python solution

class Solution:
    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:
        usageLimits.sort()
        k, n = 0, len(usageLimits)
        for i in range(n):
            if usageLimits[i] > k:
                k += 1
                usageLimits[i] -= k
            if i + 1 < n:
                usageLimits[i + 1] += usageLimits[i]
        return k

Complexity

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 2790. Maximum Number of Groups With Increasing Length is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems