HardNo. 2790
Maximum Number of Groups With Increasing Length — LeetCode 2790 Python Solution
- Pattern
- Monotonic Stack
- Topics
- Greedy, Array, Math, Binary Search, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
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 kComplexity
- Time
- O(log n) or O(n log n)
- Space · auxiliary
- O(1)
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
| No. | Problem | Difficulty |
|---|---|---|
| 1648 | Sell Diminishing-Valued Colored Balls | Medium |
| 2967 | Minimum Cost to Make Array Equalindromic | Medium |
| 2141 | Maximum Running Time of N Computers | Hard |
| 2333 | Minimum Sum of Squared Difference | Medium |
| 2358 | Maximum Number of Groups Entering a Competition | Medium |
| 2389 | Longest Subsequence With Limited Sum | Easy |
Frequently asked questions
- How hard is LeetCode 2790. Maximum Number of Groups With Increasing Length?
LeetCode 2790. Maximum Number of Groups With Increasing Length is rated Hard on LeetCode.
- What topics does LeetCode 2790. Maximum Number of Groups With Increasing Length cover?
LeetCode 2790. Maximum Number of Groups With Increasing Length is tagged Greedy, Array, Math, Binary Search and Sorting on LeetCode.