Welcome to Subscribe On Youtube
2790. Maximum Number of Groups With Increasing Length
Description
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:
- Each group must consist of distinct numbers, meaning that no duplicate numbers are allowed within a single group.
- Each group (except the first one) must have a length strictly greater than the previous group.
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] <= 109
Solutions
Solution 1: Sorting
This implementation uses sorting. It traverses the relevant values and updates its state as each value is processed. Ordering the data first makes the subsequent comparisons deterministic. After all required states have been considered, the maintained result is returned.
Solution 2
This implementation uses sorting. It traverses the relevant values and updates its state as each value is processed. Ordering the data first makes the subsequent comparisons deterministic. After all required states have been considered, the maintained result is returned.
-
class Solution { public int maxIncreasingGroups(List<Integer> usageLimits) { Collections.sort(usageLimits); int k = 0; long s = 0; for (int x : usageLimits) { s += x; if (s > k) { ++k; s -= k; } } return k; } } -
class Solution { public: int maxIncreasingGroups(vector<int>& usageLimits) { sort(usageLimits.begin(), usageLimits.end()); int k = 0; long long s = 0; for (int x : usageLimits) { s += x; if (s > k) { ++k; s -= k; } } return k; } }; -
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 # Solution 2 class Solution: def maxIncreasingGroups(self, usageLimits: List[int]) -> int: usageLimits.sort() k = s = 0 for x in usageLimits: s += x if s > k: k += 1 s -= k return k -
func maxIncreasingGroups(usageLimits []int) int { sort.Ints(usageLimits) s, k := 0, 0 for _, x := range usageLimits { s += x if s > k { k++ s -= k } } return k } -
function maxIncreasingGroups(usageLimits: number[]): number { usageLimits.sort((a, b) => a - b); let k = 0; let s = 0; for (const x of usageLimits) { s += x; if (s > k) { ++k; s -= k; } } return k; }