Minimum Operations to Make Array Non Decreasing
Real-world version: Trimming the Parcel BaysThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def min_operations(nums: list[int]) -> int:public long minOperations(int[] nums)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's