# Maximum Number of Groups With Increasing Length
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-number-of-groups-with-increasing-length)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-groups-with-increasing-length
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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 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 <= 105`
* `1 <= usageLimits[i] <= 109`

# Approaches
## Brute-Force with Backtracking
This approach explores the problem space by trying to build groups one by one recursively. It tries all possible valid group compositions at each step. A recursive function would try to form the `k`-th group, given the state of usage of numbers and the size of the `(k-1)`-th group.
**Time:** O(2^N * N!) or worse. The number of subsets of numbers is `2^N`, and for each subset, we can arrange them in groups. The branching factor is huge. This is computationally infeasible. · **Space:** O(N * k_max) for the recursion stack, where `k_max` is the maximum number of groups.
**Pros:** Conceptually simple in terms of exploring all possibilities.
**Cons:** Extremely inefficient and will time out for all but the smallest inputs.; Complex to implement correctly due to managing combinations and state.
### Explanation
The core idea is to define a recursive function, say `findMaxGroups(groupNum, prevGroupSize, usage)`, which tries to find the maximum number of additional groups that can be formed starting from group `groupNum`.
- `groupNum`: The index of the current group to form (e.g., 1, 2, 3...).
- `prevGroupSize`: The size of the previously formed group. The current group must be larger than this.
- `usage`: An array or map to track the current usage of each number `i`, ensuring it doesn't exceed `usageLimits[i]`.

The function would work as follows:
1. Iterate through all possible sizes `s` for the current group, where `s > prevGroupSize`.
2. For each size `s`, iterate through all combinations of `s` distinct numbers.
3. For each combination, check if using these numbers is valid (i.e., their usage doesn't exceed their limits).
4. If a valid group can be formed, make a recursive call: `1 + findMaxGroups(groupNum + 1, s, updatedUsage)`.
5. The function returns the maximum value found among all valid choices. The base case is when no valid group can be formed, in which case it returns 0.

This approach is highly inefficient because it explores a vast number of possibilities (combinations of sizes and numbers) and would lead to a Time Limit Exceeded verdict on any reasonably sized input.
### Algorithm
*   Define a recursive function `solve(k, prev_size, current_usages)` where `k` is the group number to form, `prev_size` is the size of group `k-1`, and `current_usages` tracks usage of each number.
*   The function aims to maximize the number of groups starting from `k`.
*   Initialize `max_groups = 0`.
*   Iterate through all possible sizes `s` for group `k`, from `prev_size + 1` to `n`.
*   For each size `s`, generate all combinations of `s` distinct numbers from `0` to `n-1`.
*   For each combination:
    *   Check if this group is valid by comparing required usages with `usageLimits - current_usages`.
    *   If valid, create `next_usages` by updating `current_usages`.
    *   Recursively call `res = 1 + solve(k + 1, s, next_usages)`.
    *   Update `max_groups = max(max_groups, res)`.
*   Return `max_groups`.
*   The initial call would be `solve(1, 0, initial_usages)`.

## Binary Search on the Answer
This approach leverages the monotonic nature of the problem. If we can form `k` groups, we can also form `k-1` groups. This allows us to binary search for the maximum possible number of groups, `k`. For each `k` we test, we need an efficient way to determine if it's possible to form `k` groups.
**Time:** O(N log N). Sorting takes `O(N log N)`. The binary search performs `O(log N)` iterations, and each call to `canForm` takes `O(N)`. So, the total time is `O(N log N + N log N) = O(N log N)`. · **Space:** O(N) or O(log N) depending on the sort implementation. In Java, `Arrays.sort` for primitives uses a dual-pivot quicksort which takes `O(log N)` space on average. If we consider the copy of the list to an array, it's `O(N)`.
**Pros:** Much more efficient than brute-force.; Guaranteed to find the optimal solution due to the monotonic property.
**Cons:** Less efficient than the direct greedy approach because of the `log N` factor from the binary search, which involves multiple passes over the data.
### Explanation
The search space for the answer `k` is from `0` to `n` (the number of elements in `usageLimits`), as we need at least `k` distinct numbers to form the `k`-th group.

The main challenge is the `can_form(k)` function. This function checks if it's possible to form `k` groups with increasing lengths. To maximize our chances, we should use the minimum possible lengths: `1, 2, ..., k`. The total number of elements required is the sum `1 + 2 + ... + k = k * (k + 1) / 2`.

A greedy strategy can be used within `can_form(k)`. We sort `usageLimits` to handle the scarcest numbers first. We iterate through the sorted limits, accumulating the total number of elements available (`total_elements`). At each step, we check if `total_elements` is sufficient to form the next group.

The `can_form(k)` function works as follows:
1.  It takes a potential number of groups `k` and the sorted `usageLimits` array.
2.  It simulates the greedy group formation process. It maintains a count of `groups_formed` and `total_elements` collected so far.
3.  It iterates through the sorted `usageLimits`. In each step, it adds the current limit to `total_elements`.
4.  It checks if the `total_elements` collected are enough to form `groups_formed + 1` groups. The required number of elements for `m` groups is `m * (m + 1) / 2`.
5.  If `total_elements` is sufficient for `groups_formed + 1` groups, it increments `groups_formed`.
6.  After iterating through all limits, it returns `true` if `groups_formed >= k`, and `false` otherwise.

The main function performs a binary search. It sorts `usageLimits` once. Then, it repeatedly calls `can_form(mid)` to narrow down the search range for `k`.
```java
import java.util.Arrays;
import java.util.List;

class Solution {
    public int maxIncreasingGroups(List<Integer> usageLimits) {
        long[] limits = new long[usageLimits.size()];
        for (int i = 0; i < usageLimits.size(); i++) {
            limits[i] = usageLimits.get(i);
        }
        Arrays.sort(limits);

        int low = 0, high = usageLimits.size();
        int ans = 0;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canForm(mid, limits)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean canForm(int k, long[] limits) {
        if (k == 0) {
            return true;
        }
        long totalElements = 0;
        int groupsFormed = 0;
        
        for (long limit : limits) {
            totalElements += limit;
            long nextGroupNum = groupsFormed + 1;
            // Using long to prevent overflow for k*(k+1)/2
            long requiredElements = nextGroupNum * (nextGroupNum + 1) / 2;
            
            if (totalElements >= requiredElements) {
                groupsFormed++;
            }
        }
        return groupsFormed >= k;
    }
}
```
### Algorithm
*   Sort the `usageLimits` array in non-decreasing order. This is done once.
*   Initialize binary search variables: `low = 0`, `high = n`, `ans = 0`.
*   While `low <= high`:
    *   Calculate `mid = low + (high - low) / 2`.
    *   If `can_form(mid, usageLimits)` is true:
        *   This means `mid` groups are possible. We store it as a potential answer and try for more.
        *   `ans = mid`.
        *   `low = mid + 1`.
    *   Else (`can_form(mid, usageLimits)` is false):
        *   `mid` groups are not possible. We need to try a smaller number.
        *   `high = mid - 1`.
*   Return `ans`.

*   **can_form(k, sorted_limits)** function:
    *   Initialize `groups_formed = 0`, `total_elements = 0`.
    *   Iterate through each `limit` in `sorted_limits`:
        *   `total_elements += limit`.
        *   Let `next_group_num = groups_formed + 1`.
        *   Calculate `required_elements = next_group_num * (next_group_num + 1) / 2`.
        *   If `total_elements >= required_elements`:
            *   `groups_formed = next_group_num`.
    *   Return `groups_formed >= k`.

## Greedy Approach with Sorting
This is the most efficient approach. The core idea is that to maximize the number of groups, we should be as frugal as possible with the elements. By sorting the `usageLimits`, we can process numbers with smaller limits first. We greedily form groups whenever we accumulate enough elements to satisfy the requirements for the next group size.
**Time:** O(N log N). The dominant operation is sorting the `usageLimits` array. The subsequent loop is a single pass, taking `O(N)` time. · **Space:** O(log N) or O(N). `Collections.sort` in Java for Lists uses Timsort, which requires `O(N)` space in the worst case. If it were an array of primitives, it would be `O(log N)`.
**Pros:** Optimal time complexity for this problem.; Simpler to implement than the binary search approach.; More efficient in practice than binary search as it only requires a single pass over the data after sorting.
**Cons:** The correctness of the greedy strategy is not immediately obvious without careful reasoning.
### Explanation
The intuition is that if we can form `k` groups, the total number of elements used must be at least `1 + 2 + ... + k = k * (k + 1) / 2`. The greedy choice is to form a new group as soon as this condition is met.

1.  **Sort `usageLimits`**: We sort the `usageLimits` array in non-decreasing order. This allows us to consider the numbers with the tightest constraints first. By accumulating their counts, we see if they can collectively support forming groups.
2.  **Iterate and Accumulate**: We iterate through the sorted limits, maintaining a running sum of the limits encountered so far (`total_elements`) and the number of groups we have successfully formed (`groups`).
3.  **Greedy Check**: In each iteration, after adding the current `limit` to `total_elements`, we check if we can form the next group. If we have formed `groups` groups so far, the next one would be group `groups + 1`. The total number of elements needed to form `groups + 1` groups of minimal sizes `1, 2, ..., groups + 1` is `(groups + 1) * (groups + 2) / 2`.
4.  **Form Group**: If `total_elements` is greater than or equal to this required amount, it means we have enough "material" to form the `(groups + 1)`-th group. So, we increment `groups`. The logic holds because by processing sorted limits, we ensure that by the time we form group `k`, we have already considered at least `k` distinct numbers (since `groups` can't grow faster than the loop index). This satisfies the distinctness constraint for the largest group.

This single pass after sorting is sufficient to find the maximum number of groups.
```java
import java.util.Collections;
import java.util.List;

class Solution {
    public int maxIncreasingGroups(List<Integer> usageLimits) {
        Collections.sort(usageLimits);
        
        long totalElements = 0;
        int groups = 0;
        
        for (int limit : usageLimits) {
            totalElements += limit;
            long nextGroupCount = groups + 1;
            
            // Check if the accumulated elements are sufficient to form 'nextGroupCount' groups
            // with sizes 1, 2, ..., nextGroupCount.
            // The total elements required is the sum of an arithmetic series.
            if (totalElements >= nextGroupCount * (nextGroupCount + 1) / 2) {
                groups++;
            }
        }
        
        return groups;
    }
}
```
### Algorithm
*   Sort the `usageLimits` array in non-decreasing order.
*   Initialize `groups = 0` and `total_elements = 0L` (use long to prevent overflow).
*   Iterate through each `limit` in the sorted `usageLimits`:
    *   Add the current `limit` to `total_elements`.
    *   Let `k = groups + 1`. This is the number of groups we are trying to form now.
    *   The minimum total elements required for `k` groups is `k * (k + 1) / 2`.
    *   If `total_elements >= (long)k * (k + 1) / 2`:
        *   We can form `k` groups. Update `groups = k`.
*   Return `groups`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```