0650HardArrayMathGreedy

Cutting Crates Into a Rising Manifest

Tracked in this browser only

Trains the technique from

LeetCode 2366Minimum Replacements to Sort the Array

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 freight manifest lists crate weights in loading order as weights. The loader will only accept the manifest when the weights never decrease as you read it from the first entry to the last.

One cut takes a single crate of weight w and replaces it with two crates whose weights are positive whole numbers adding up to w. The two new crates take the cut crate's place in the manifest, one after the other, so the manifest gets one entry longer. Either of the new crates may be cut again later.

Return the least number of cuts that makes the manifest never decrease.

Examples

Example 1

Input: weights = [12, 8, 6]
Output: 3

Cut the 8 into 4 and 4, then cut the 12 into 4 and 8 and cut that 8 into 4 and 4. The manifest now reads 4, 4, 4, 4, 4, 6, which never decreases, after three cuts.

Example 2

Input: weights = [10, 3, 3]
Output: 3

Three cuts turn the 10 into 2, 2, 3 and 3, leaving the manifest reading 2, 2, 3, 3, 3, 3, which never decreases.

Example 3

Input: weights = [2, 4, 6]
Output: 0

The manifest already never decreases, so no cut is needed.

Constraints

1 <= weights.length <= 10^5
1 <= weights[i] <= 10^9
The answer is at most 10^15 for every input allowed above.

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 min_crate_splits(weights: list[int]) -> int:

Java

public long minCrateSplits(int[] weights)

The intended approach

Time O(n): one backwards pass with constant work per crate.Space O(1): a running ceiling and a running cut count.

The last crate is never worth cutting, and once the crates to the right of a position are settled, the only thing that matters about them is the smallest weight standing immediately to the right. So sweep from the back holding that ceiling. A crate at or below the ceiling stays whole and becomes the new ceiling. A heavier crate of weight `w` needs at least `ceil(w / ceiling)` pieces to get every piece under the ceiling, which costs one cut fewer than that; splitting `w` as evenly as possible over that many pieces makes the smallest piece `w // pieces`, and that becomes the ceiling for the crates further left.

Pythonentry point: min_crate_splits

def min_crate_splits(weights):
    # Walk from the last crate backwards carrying the heaviest weight the crate to
    # the left is allowed to end on. A crate above that ceiling is cut into the
    # fewest pieces that all fit under it, and the pieces are made as even as
    # possible so the new ceiling stays as high as it can.
    # O(n) time, O(1) space.
    ceiling = weights[-1]
    splits = 0
    for i in range(len(weights) - 2, -1, -1):
        w = weights[i]
        if w <= ceiling:
            ceiling = w
        else:
            pieces = (w + ceiling - 1) // ceiling
            splits += pieces - 1
            ceiling = w // pieces
    return splits

The obvious version

A finished manifest replaces each original crate by some list of positive weights adding up to it, and that list must itself never decrease, so it is one of the partitions of the weight written in non-decreasing order. Enumerate those partitions for each crate and search over the choices from left to right, carrying the last weight emitted so far and memoising on the position together with that weight. The cost of a choice is its number of pieces minus one.

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_min_crate_splits(weights):
    def cuts_of(x):
        found = []

        def walk(rest, low, cur):
            if rest == 0:
                found.append(tuple(cur))
                return
            for p in range(low, rest + 1):
                cur.append(p)
                walk(rest - p, p, cur)
                cur.pop()

        walk(x, 1, [])
        return found

    n = len(weights)
    cache = {}
    table = {}

    def solve(i, prev):
        if i == n:
            return 0
        key = (i, prev)
        if key in cache:
            return cache[key]
        if weights[i] not in table:
            table[weights[i]] = cuts_of(weights[i])
        best = None
        for pieces in table[weights[i]]:
            if pieces[0] < prev:
                continue
            rest = solve(i + 1, pieces[-1])
            if rest is None:
                continue
            cost = len(pieces) - 1 + rest
            if best is None or cost < best:
                best = cost
        cache[key] = best
        return best

    return solve(0, 1)

How this problem was checked

Reference solution executed against 14 test cases — 14 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