LeetCode Problem 2790

Difficulty: 🔴 Hard
Topics: Array, Math, Binary Search, Greedy, Sorting

Solution

LeetCode 2790 - Maximum Number of Groups With Increasing Length

Problem Understanding

We are given an array usageLimits where usageLimits[i] tells us how many times the number i can be used across all groups.

The numbers available are exactly 0 through n - 1, where n is the length of the array. We want to create as many groups as possible while satisfying two constraints.

First, every group must contain distinct numbers. A number may appear in multiple different groups, provided its total usage across all groups does not exceed its limit, but it cannot appear twice within the same group.

Second, group sizes must be strictly increasing. If the first group has size 1, the next might have size 2, then size 3, and so on. More generally, if one group has length k, the next must have length greater than k.

Our goal is to maximize the total number of groups.

A key observation is that if we create g groups, the smallest possible group lengths are:

1, 2, 3, ..., g

Any other strictly increasing sequence would require at least as many elements. Therefore, if we can form g groups, we can always think of them as requiring exactly:

1 + 2 + 3 + ... + g = g(g + 1)/2

total element placements.

The constraints are large:

• n ≤ 100,000
• usageLimits[i] ≤ 1,000,000,000

This immediately rules out any solution that attempts to explicitly construct groups or simulate individual usages. We need an algorithm close to O(n log n).

Several edge cases are important:

• A single element with an enormous usage limit.
• Many elements with usage limit 1.
• Extremely unbalanced limits such as [1,1,1,1000000000].
• Large arrays where the answer is close to n.
• Cases where the total usage count is large enough, but distinctness constraints prevent forming additional groups.

The challenge is not merely counting total available usages. Because a number can appear at most once per group, large limits cannot always be fully exploited.

Approaches

Brute Force

A brute force approach would attempt to build groups one at a time.

For every new group, we could try to select enough numbers that still have remaining capacity. We would repeatedly choose valid numbers, decrease their remaining usages, and continue until no larger group can be formed.

This eventually finds the correct answer because it explicitly simulates the process. However, it is computationally infeasible. The usage limits can be as large as 10^9, and there may be 100,000 numbers. Simulating group construction would require enormous amounts of work.

Key Insight

The crucial observation is that after sorting the usage limits, we do not need to know the actual composition of the groups.

Suppose we process the capacities from smallest to largest.

Let:

available = total usable capacity accumulated so far

When considering a new number with limit x, we add its contribution to available.

If we have already formed groups groups, then forming one more group requires:

groups + 1

additional positions.

Whenever the accumulated capacity becomes large enough to support the next group size, we create that group and subtract its required size from the accumulated capacity.

The reason this works is that sorting ensures smaller capacities are handled first. Any excess capacity from previous elements can be carried forward and used later. The greedy choice of immediately forming the next possible group never hurts because larger future groups only require more capacity.

This leads to a very elegant greedy solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential or worse	O(n)	Attempts to explicitly construct groups
Optimal Greedy + Sorting	O(n log n)	O(1) extra, excluding sort	Uses accumulated capacity and greedily forms groups

Algorithm Walkthrough

Step 1

Sort usageLimits in nondecreasing order.

Sorting allows us to process smaller capacities first and reason about the total available capacity in a structured way.

Step 2

Maintain two variables:

• groups, the number of groups already formed
• available, the unused capacity accumulated so far

Initially:

groups = 0
available = 0

Step 3

Iterate through the sorted usage limits.

For each value limit:

available += limit

This represents all remaining usages that can potentially contribute to future groups.

Step 4

Check whether enough capacity exists to create the next group.

The next group would have size:

groups + 1

If:

available >= groups + 1

then we can form this group.

Step 5

Create the group greedily.

available -= groups + 1
groups += 1

The required capacity is consumed, and we move on to searching for the next larger group.

Step 6

Continue until all usage limits have been processed.

The final value of groups is the maximum number of groups that can be formed.

Why it works

After sorting, every processed usage limit contributes capacity that can be distributed among current and future groups. The invariant is that available stores unused capacity remaining after constructing the maximum possible number of groups so far.

Whenever available reaches the size required for the next group, delaying that group provides no advantage because future groups are even larger. Therefore, greedily forming a group immediately is always optimal. The algorithm never wastes capacity and always constructs the maximum feasible number of increasing-length groups.

Python Solution

from typing import List

class Solution:
    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:
        usageLimits.sort()

        groups = 0
        available = 0

        for limit in usageLimits:
            available += limit

            if available >= groups + 1:
                groups += 1
                available -= groups

        return groups

The implementation begins by sorting the array. This guarantees that smaller capacities are processed first.

The variable available stores the amount of unused capacity accumulated from all processed elements. Every usage limit contributes its entire capacity to this pool.

The variable groups tracks how many groups have already been formed. Whenever the accumulated capacity reaches the size required for the next group, the algorithm immediately creates that group.

Notice that after incrementing groups, the code subtracts groups from available. This works because the newly created group has size equal to the updated value of groups.

At the end of the iteration, groups contains the maximum number of increasing-length groups.

Go Solution

import "sort"

func maxIncreasingGroups(usageLimits []int) int {
	sort.Ints(usageLimits)

	groups := 0
	var available int64 = 0

	for _, limit := range usageLimits {
		available += int64(limit)

		if available >= int64(groups+1) {
			groups++
			available -= int64(groups)
		}
	}

	return groups
}

The Go implementation follows exactly the same logic as the Python version.

One important difference is the use of int64 for available. Since there can be up to 100,000 elements and each usage limit can be as large as 10^9, the total accumulated capacity can reach approximately 10^14, which exceeds a 32-bit integer range. Using int64 prevents overflow.

The input slice is sorted in place using sort.Ints.

Worked Examples

Example 1

usageLimits = [1,2,5]

After sorting:

[1,2,5]

Limit	Available Before	Available After Add	Next Group Size	Group Formed?	Available After Use	Groups
1	0	1	1	Yes	0	1
2	0	2	2	Yes	0	2
5	0	5	3	Yes	2	3

Final answer:

3

Example 2

usageLimits = [2,1,2]

After sorting:

[1,2,2]

Limit	Available Before	Available After Add	Next Group Size	Group Formed?	Available After Use	Groups
1	0	1	1	Yes	0	1
2	0	2	2	Yes	0	2
2	0	2	3	No	2	2

Final answer:

2

Example 3

usageLimits = [1,1]

After sorting:

[1,1]

Limit	Available Before	Available After Add	Next Group Size	Group Formed?	Available After Use	Groups
1	0	1	1	Yes	0	1
1	0	1	2	No	1	1

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the running time
Space	O(1) extra	Only a few variables are used beyond the sort

The main cost comes from sorting the array. After sorting, the algorithm performs a single linear scan. No auxiliary data structures proportional to n are required, so the extra space usage remains constant apart from the sorting implementation itself.

Test Cases

from typing import List

s = Solution()

assert s.maxIncreasingGroups([1, 2, 5]) == 3  # Example 1
assert s.maxIncreasingGroups([2, 1, 2]) == 2  # Example 2
assert s.maxIncreasingGroups([1, 1]) == 1      # Example 3

assert s.maxIncreasingGroups([1]) == 1         # Single element
assert s.maxIncreasingGroups([1000000000]) == 1  # Huge capacity, only one number

assert s.maxIncreasingGroups([1, 1, 1]) == 2  # Groups of sizes 1 and 2
assert s.maxIncreasingGroups([1, 1, 1, 1]) == 2  # Insufficient for size 3

assert s.maxIncreasingGroups([2, 2, 2]) == 3  # Can form 1,2,3

assert s.maxIncreasingGroups([1, 1, 1, 100]) == 3  # Highly unbalanced

assert s.maxIncreasingGroups([3, 3, 3, 3]) == 4  # Enough capacity for all groups

assert s.maxIncreasingGroups([1, 2, 3, 4, 5]) == 5  # Increasing capacities

assert s.maxIncreasingGroups([100, 100, 100, 100, 100]) == 5  # Large capacities

assert s.maxIncreasingGroups([1, 7, 7, 7, 7]) == 5  # Small first limit

Test Summary

Test	Why
[1,2,5]	Official example
[2,1,2]	Official example
[1,1]	Official example
[1]	Minimum size input
[1000000000]	Large usage limit with one number
[1,1,1]	Exact capacity for two groups
[1,1,1,1]	Cannot build third group
[2,2,2]	Every number reusable
[1,1,1,100]	Extremely unbalanced capacities
[3,3,3,3]	Forms all possible group sizes
[1,2,3,4,5]	Naturally increasing capacities
[100,100,100,100,100]	Large capacities everywhere
[1,7,7,7,7]	Small bottleneck followed by large capacities

Edge Cases

Single Number

Consider:

[1000000000]

A naive solution might think the enormous capacity allows many groups. However, there is only one distinct number available. Since each group requires distinct elements, only one group of size 1 can exist. The greedy algorithm correctly returns 1.

Many Capacity-One Elements

Consider:

[1,1,1,1]

The total capacity is 4, but three groups would require:

1 + 2 + 3 = 6

positions. The algorithm tracks accumulated capacity and correctly determines that only two groups can be formed.

Extremely Unbalanced Limits

Consider:

[1,1,1,1000000000]

A naive strategy based purely on total capacity might overestimate the answer. The distinctness constraint means the huge limit on one number cannot fully compensate for the lack of distinct numbers. Sorting and greedily accumulating capacity correctly account for this restriction and produce the optimal number of groups.

Very Large Usage Limits

The sum of all usage limits can reach roughly:

100000 × 10^9 = 10^14

This exceeds 32-bit integer capacity. The Go solution uses int64 for accumulated capacity, ensuring correctness even at the maximum constraint limits. The Python solution naturally supports arbitrarily large integers.