LeetCode 2790 (Hard). Maximum Number of Groups With Increasing Length. Solution of the day. O(N logN). Math
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 <= 10^5
1 <= usageLimits[i] <= 10^9
Approach
- Sorting the usageLimits array: The first step is to sort the input array usageLimits in ascending order. Sorting takes O(NlogN) time complexity, where N is the length of the usageLimits array.
- Tracking the total and count: The total variable is used to keep track of the cumulative sum of elements in the sorted usageLimits array. The count variable represents the number of groups created so far that satisfy the conditions.
- Iterating through the sorted array: The function iterates through the sorted array using a for loop. For each element at index i, it adds the value to the total. The purpose of the total is to keep track of the total number of allowed occurrences across all groups formed so far.
- Checking the conditions: After adding an element to the total, the function checks whether the current total value is greater than or equal to the required sum for the next group. The required sum for the next group is calculated as ((count + 1) * (count + 2)) / 2. Here, count + 1 represents the next group's length, and (count + 2) / 2 represents the sum of elements from 0 to count + 1. If the total is greater than or equal to this required sum, it means that we can create another group satisfying the conditions.
- Incrementing the count: If the condition in step 4 is true, the count is incremented, indicating that another group can be formed.
- Returning the result: After iterating through the entire sorted array, the count variable will represent the maximum number of groups that can be created while satisfying the conditions. The function returns this count.
Complexity
Time complexity: O(N logN).
The time complexity of this solution is dominated by the sorting step, making it O(N logN), where N is the length of the input array usageLimits. The rest of the operations involve simple arithmetic and comparisons, which take linear time. Therefore, the overall time complexity of the function is O(N logN).
Code (Swift)
Sources: Github