2790. Maximum Number of Groups With Increasing Length LeetCode Solution
In this guide, you will get 2790. Maximum Number of Groups With Increasing Length LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Groups With Increasing Length problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Number of Groups With Increasing Length
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.
2790. Maximum Number of Groups With Increasing Length LeetCode Solution in C++
class Solution {
public:
int maxIncreasingGroups(vector<int>& usageLimits) {
int ans = 1; // the next target length
long availableLimits = 0;
ranges::sort(usageLimits);
for (const int usageLimit : usageLimits) {
availableLimits += usageLimit;
// Can create groups 1, 2, ..., ans.
if (availableLimits >= ans * static_cast<long>(ans + 1) / 2)
++ans;
}
return ans - 1;
}
}; /* code provided by PROGIEZ */
2790. Maximum Number of Groups With Increasing Length LeetCode Solution in Java
class Solution {
public int maxIncreasingGroups(List<Integer> usageLimits) {
int ans = 1; // the next target length
long availableLimits = 0;
Collections.sort(usageLimits);
for (final int usageLimit : usageLimits) {
availableLimits += usageLimit;
// Can create groups 1, 2, ..., ans.
if (availableLimits >= ans * (long) (ans + 1) / 2)
++ans;
}
return ans - 1;
}
} // code provided by PROGIEZ
2790. Maximum Number of Groups With Increasing Length LeetCode Solution in Python
class Solution:
def maxIncreasingGroups(self, usageLimits: list[int]) -> int:
ans = 1 # the next target length
availableLimits = 0
for usageLimit in sorted(usageLimits):
availableLimits += usageLimit
# Can create groups 1, 2, ..., ans.
if availableLimits >= ans * (ans + 1) // 2:
ans += 1
return ans - 1 # code by PROGIEZ
