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. 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 themaximum number of groups you can create while satisfying these conditions.

Examples

Example 1

1
2
3
4
5
6
7
8
9

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

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6
7

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

Solution

Method 1 – Greedy + Binary Search

Intuition

To maximize the number of groups, we want to distribute the available usages to groups of increasing size. The smallest group has size 1, the next size 2, and so on. We can use binary search to find the largest k such that the sum of the first k natural numbers (1+2+…+k) can be formed with the available usage limits.

Approach

  1. Sort the usageLimits in descending order (optional, but helps with greedy allocation).
  2. Use binary search to find the maximum k such that the sum of the first k natural numbers is less than or equal to the total number of usages available.
  3. For each candidate k, check if it’s possible to form groups of size 1 to k using the available usages (by simulating the allocation or using a greedy check).
  4. Return the largest possible k.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int maxIncreasingGroups(vector<int>& usageLimits) {
        sort(usageLimits.begin(), usageLimits.end());
        long long sum = 0;
        int ans = 0;
        for (int x : usageLimits) {
            sum += x;
            if (sum >= (long long)(ans + 1) * (ans + 2) / 2) ans++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import "sort"
func maxIncreasingGroups(usageLimits []int) int {
    sort.Ints(usageLimits)
    sum, ans := 0, 0
    for _, x := range usageLimits {
        sum += x
        if sum >= (ans+1)*(ans+2)/2 {
            ans++
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import java.util.*;
class Solution {
    public int maxIncreasingGroups(int[] usageLimits) {
        Arrays.sort(usageLimits);
        long sum = 0;
        int ans = 0;
        for (int x : usageLimits) {
            sum += x;
            if (sum >= (long)(ans + 1) * (ans + 2) / 2) ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun maxIncreasingGroups(usageLimits: IntArray): Int {
        usageLimits.sort()
        var sum = 0L
        var ans = 0
        for (x in usageLimits) {
            sum += x
            if (sum >= (ans + 1L) * (ans + 2) / 2) ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def maxIncreasingGroups(self, usageLimits: list[int]) -> int:
        usageLimits.sort()
        total = 0
        ans = 0
        for x in usageLimits:
            total += x
            if total >= (ans + 1) * (ans + 2) // 2:
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn max_increasing_groups(mut usage_limits: Vec<i32>) -> i32 {
        usage_limits.sort();
        let mut sum = 0i64;
        let mut ans = 0;
        for &x in &usage_limits {
            sum += x as i64;
            if sum >= ((ans + 1) * (ans + 2) / 2) as i64 {
                ans += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    maxIncreasingGroups(usageLimits: number[]): number {
        usageLimits.sort((a, b) => a - b);
        let sum = 0, ans = 0;
        for (const x of usageLimits) {
            sum += x;
            if (sum >= (ans + 1) * (ans + 2) / 2) ans++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), for sorting the array and a single pass.
  • 🧺 Space complexity: O(1), as we use only a few variables for computation.