0613MediumArrayGreedy

Trimming the Parcel Bays

Tracked in this browser only

Trains the technique from

LeetCode 3914Minimum Operations to Make Array Non Decreasing

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 has n bays in a row. Bay i currently holds nums[i] parcels.

One operation takes a single parcel out of one bay and off the site. A bay can never hold a negative number of parcels, and parcels are never added or moved between bays.

The depot passes inspection when the counts read left to right never go down, that is when nums[i] <= nums[i + 1] holds for every neighbouring pair. Return the smallest number of operations that makes the depot pass.

Examples

Example 1

Input: nums = [6, 2, 8, 4]
Output: 8

Removing four parcels from bay 0 and four from bay 2 leaves the counts `[2, 2, 4, 4]`, which never go down, for eight operations in total.

Example 2

Input: nums = [1, 3, 6, 9]
Output: 0

The counts already rise from left to right, so nothing has to be removed.

Example 3

Input: nums = [5, 4, 1]
Output: 7

Taking four parcels from bay 0 and three from bay 1 leaves `[1, 1, 1]`, for seven operations.

Constraints

1 <= n == nums.length <= 10^5
1 <= nums[i] <= 10^9
The answer never exceeds 10^14.

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_operations(nums: list[int]) -> int:

Java

public long minOperations(int[] nums)

The intended approach

Time O(n) — a single right-to-left pass.Space O(1) — a running ceiling and a running total.

The last bay is never worth touching, so the scan runs from the right end leftwards carrying one number: the largest count a bay may keep without breaking the order to its right. When a bay already sits at or below that ceiling it keeps everything and becomes the new ceiling; when it sits above, the excess is removed and the ceiling stays where it was. Summing the excesses gives the answer, and only two integers are held at a time.

Pythonentry point: min_operations

def min_operations(nums):
    # O(n) time, O(1) extra space. Walk the bays from the right end. A bay can
    # never be allowed to hold more than the smallest count that survives to
    # its right, so carry that surviving ceiling backwards; whatever a bay
    # holds above the ceiling has to be removed, and the ceiling for the next
    # bay to the left is the smaller of the two counts.
    ceiling = nums[-1]
    removals = 0
    for i in range(len(nums) - 2, -1, -1):
        if nums[i] > ceiling:
            removals += nums[i] - ceiling
        else:
            ceiling = nums[i]
    return removals

The obvious version

For each bay, scan every bay strictly to its right to find the smallest count anywhere in that suffix, then charge the difference between the bay's own count and the smaller of the two. Add those charges up.

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_operations(nums):
    n = len(nums)
    total = 0
    for i in range(n):
        smallest = nums[i]
        for j in range(i + 1, n):
            if nums[j] < smallest:
                smallest = nums[j]
        total += nums[i] - smallest
    return total

How this problem was checked

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