You are given an integer array nums of length n.

In one operation, you may choose any subarray nums[l..r] and increase each element in that subarray by x, where x is any positive integer.

Return the minimum possible sum of the values of x across all operations required to make the array non-decreasing.

An array is non-decreasing if nums[i] <= nums[i + 1] for all 0 <= i < n - 1.

In simpler terms, you start with an array and want to transform it into a non-decreasing array. Your only tool is picking a contiguous segment (a subarray) and adding the same positive value x to every element in that segment. Each time you do this, the cost is x. You can perform as many operations as you want, choosing different subarrays and different values of x each time. The goal is to find the smallest total cost (the sum of all the x values used) needed so that, after all operations, no element is greater than the element immediately following it.

Note that the operation can only increase elements, never decrease them. This means that whenever there is a "drop" in the array (where nums[i] > nums[i + 1]), you must raise the later elements to close that gap. Since you can always extend a subarray to include everything from a certain point to the end of the array, lifting later elements never harms earlier comparisons — so the only real requirement is to cover each individual drop between adjacent elements.

The key observation is that our operation can only add value to elements, never remove it. So whenever we encounter a place where the array decreases — that is, where nums[i] > nums[i + 1] — we are forced to lift nums[i + 1] (and possibly elements after it) upward to repair that drop.

Let's think about how much we must lift at each position. Consider any adjacent pair nums[i] and nums[i + 1]:

• If nums[i + 1] >= nums[i], this pair is already in the correct order, and no operation is needed here.
• If nums[i + 1] < nums[i], there is a "drop" of size nums[i] - nums[i + 1]. To fix it, the element at position i + 1 must be raised by at least nums[i] - nums[i + 1] so that it reaches the level of nums[i].

Now, why can we treat each drop independently and simply add them all up? Because of a very helpful freedom: a subarray can always be chosen to extend all the way to the end of the array. When we raise nums[i + 1], we can raise every element from i + 1 to the last index by the same amount. Lifting later elements by extra amounts never breaks any earlier ordering — it only pushes the tail of the array higher, which keeps the right side "tall enough." This means fixing one drop never creates a new drop somewhere else.

Because every drop can be repaired without interfering with the others, the minimum total cost is just the sum of the sizes of all the drops. For each adjacent pair, the contribution is max(nums[i] - nums[i + 1], 0) — we pay for the gap when there is a drop, and pay nothing when the order is already fine.

Summing this quantity over all adjacent pairs gives exactly the minimum total x we must spend, which leads directly to the one-line greedy solution.

Pattern Learn more about Greedy patterns.

Solution 1: Greedy

We can traverse the array from left to right and calculate the difference between each pair of adjacent elements. If the current element is smaller than the previous one, we need to increase the current element so that it is at least equal to the previous element. The amount to increase is the difference between the previous element and the current element.

Let's break down how this translates into code:

1. Iterate over adjacent pairs. We walk through every consecutive pair (a, b) in the array, where a = nums[i] and b = nums[i + 1]. In Python, the pairwise(nums) helper conveniently yields these pairs one at a time: (nums[0], nums[1]), (nums[1], nums[2]), and so on.

2. Measure each drop. For each pair (a, b), we compute max(a - b, 0):

   • When a > b, the array drops by a - b at this position, so this is the amount we must add to repair the gap.
   • When a <= b, the pair is already in non-decreasing order, so a - b is zero or negative, and max(a - b, 0) correctly contributes 0.

3. Accumulate the total. We add up all these per-pair contributions with sum(...). As reasoned earlier, each drop can be fixed independently without affecting the others, so this sum is exactly the minimum total value of x required.

This gives the compact one-liner:

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        return sum(max(a - b, 0) for a, b in pairwise(nums))

Complexity Analysis:

• Time complexity: O(n), where n is the length of nums. We make a single pass over the array, processing each adjacent pair once.
• Space complexity: O(1). We only keep a running sum; the generator expression produces pairs lazily without building any extra list.