0636MediumArrayBinary Search

Smallest Tallest Stack After Splits

Tracked in this browser only

Trains the technique from

LeetCode 1760Minimum Limit of Balls in a Bag

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A depot floor holds several stacks of cartons. stacks[i] is the number of cartons in stack i.

One split takes a single stack off the floor and puts back two stacks in its place, each holding at least one carton, together holding exactly what the original stack held. A stack put back may be split again later. You are allowed at most splits splits, and you may also use fewer, or none at all.

The peak of the floor is the number of cartons in its tallest stack. Return the smallest peak you can leave behind.

Examples

Example 1

Input: stacks = [9, 9], splits = 2
Output: 5

Split each stack of 9 into 5 and 4, using both allowed splits. The floor then holds 5, 4, 5 and 4 cartons, so its peak is 5.

Example 2

Input: stacks = [4, 4], splits = 1
Output: 4

One split is allowed. Splitting a stack of 4 into 2 and 2 leaves the floor holding 2, 2 and 4 cartons, whose peak is 4. Carrying out no split at all also leaves a peak of 4.

Example 3

Input: stacks = [1, 1, 1], splits = 2
Output: 1

Every stack already holds a single carton and a split has to leave at least one carton on each side, so no split is possible and the peak is 1.

Constraints

1 <= stacks.length <= 10^5
1 <= splits <= 10^9
1 <= stacks[i] <= 10^9

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def minimum_size(stacks: list[int], splits: int) -> int:

Java

public int minimumSize(int[] stacks, int splits)

The intended approach

Time O(n log m) — one cost sweep per binary search step, with m the tallest stack.Space O(1) — only running counters.

Ask instead whether a given ceiling can be met. A stack of s cartons can be reduced to pieces of at most L cartons with (s - 1) // L splits, so the cost of a ceiling is that quantity added over all stacks, and a ceiling is met when the cost fits the budget. Raising the ceiling never raises the cost, so the ceilings that fit form the upper part of the range from 1 to the tallest stack, and a binary search over that range returns the first one that fits. The inner loop stops early once the cost passes the budget.

Pythonentry point: minimum_size

def minimum_size(stacks, splits):
    # O(n log m) time, O(1) space, with m the tallest stack. A ceiling L can be
    # met by cutting a stack of size s into pieces of at most L, which takes
    # (s - 1) // L splits, and a larger ceiling is never harder to meet. So the
    # feasible ceilings form an upper range and binary search finds its start.
    lo = 1
    hi = 0
    for s in stacks:
        if s > hi:
            hi = s
    while lo < hi:
        mid = (lo + hi) // 2
        need = 0
        for s in stacks:
            need += (s - 1) // mid
            if need > splits:
                break
        if need <= splits:
            hi = mid
        else:
            lo = mid + 1
    return lo

The obvious version

Try every ceiling from 1 up to the tallest stack in order, add up the splits each stack needs at that ceiling, and return the first ceiling whose total fits the budget.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_minimum_size(stacks, splits):
    top = max(stacks)
    for limit in range(1, top + 1):
        need = 0
        for s in stacks:
            need += (s - 1) // limit
        if need <= splits:
            return limit
    return top

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in