Show problems as
Classic problem #2790HardArrayMathBinary SearchGreedySorting

Maximum Number of Groups With Increasing Length

Real-world version: How Many Growing Batches Can Be Filled
Tracked in this browser only
Read Maximum Number of Groups With Increasing Length on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A store holds parts of several kinds, and stock[i] is how many parts of kind i it holds.

Fill a run of batches so that no batch holds two parts of the same kind, no kind is drawn on more times across all the batches than the store holds, and each batch after the first holds strictly more parts than the one before it.

Return the greatest number of batches that can be filled.

Examples

Example 1

Input
stock = [5, 2, 1]
Output
3

Three batches need one, two and three parts, six in all. The batch of three takes one part of each kind, the batch of two takes one of the first kind and one of the second, and the batch of one takes another of the first kind. A fourth batch would need four different kinds and only three exist.

Example 2

Input
stock = [3, 3]
Output
2

Only two kinds exist, so no batch can hold three parts without repeating a kind, which caps the run at a batch of one and a batch of two.

Example 3

Input
stock = [1000000000]
Output
1

One kind means no batch can hold two parts, so a single batch of one part is all there is, however many parts the store holds.

Constraints

  • 1 <= stock.length <= 10^5
  • 1 <= stock[i] <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_increasing_groups(stock: list[int]) -> int:
Java
public int maxIncreasingGroups(int[] stock)

More on the same topics