Minimum Operations to Make Array Non-Decreasing

Whether the whole array is sorted is decided one neighbor pair at a time — nothing but the adjacent gaps matters. An operation drops a flat slab of height x onto a contiguous stretch, and that slab changes exactly two boundaries: the gap at its left edge closes by x, and the gap at its right edge (when the slab does not run to the end of the array) opens by the same x. Everything inside the slab shifts together and stays in order.

The greedy reads that structure left to right. A pair once fixed is fixed forever: every later slab starts further right and can never touch it. So each original gap is a one-time debt, and the optimal play is to pay it the moment the scan reaches it — with a single suffix operation whose raise carries everything behind it for free.

Brute Force: Heal the Violators One at a Time

Time O(n²)Space O(n)

The most literal repair job: sweep for an out-of-order pair, patch the trailing element alone — one operation on the single-element subarray [i..i] with x equal to the gap — and restart the sweep in case the patch opened a fresh gap just to the right (index i just got taller). The process always terminates: a value only ever rises when it is itself the trailing element, so each element is healed at most once and a healed pair never reopens. The final array is guaranteed non-decreasing.

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        a = nums[:]                      # work on a copy
        total = 0
        i = 1
        while i < len(a):
            if a[i] < a[i - 1]:          # violation: a[i] trails a[i-1]
                total += a[i - 1] - a[i]
                a[i] = a[i - 1]          # one operation: subarray [i..i], x = gap
                i = 1                    # restart: a new gap may have formed
            else:
                i += 1
        return total

Trace [3,3,2,1]: index 2 is healed up by 1 to match 3, then index 3 must climb by 2 to reach the same height — spending 1 + 2 = 3 against the true answer of 2. The isolated fix pays for the climb all over again: each element is dragged to the current height of its left neighbor even when earlier raises had almost paid for it. On [5,4,3,2,1] the tally climbs to 10, where the answer is 4.

Why it is quadratic: every heal restarts a full sweep, and there can be O(n) of them, so the worst case is about O(n²) work — an array like [8,1,7,1,6] makes each sweep walk deeper before finding its violation. The working copy costs O(n) space. Correct and simple, but it overpays on exactly the arrays the suffix strategy fixes for free.

Optimal: One-Pass Deficit Sum

OptimalTime O(n)Space O(1)

Flip the question: how much debt does the original array carry? Define each pair deficit as the excess of the left member over the right member. Two facts close the deal.

Lower bound: every operation of value x can shrink the total deficit by at most x — its slab closes one gap and carries the gap along at its far edge instead of deleting it. So the sum of the deficits is a hard floor on the answer.
Match: that floor is reachable. Scanning left to right, raise the suffix starting at each violation by that pair’s deficit. Earlier fixes stay intact (a later suffix starts strictly right of them), and the carry hands the next gap to its own raise untouched — each unit of deficit is paid exactly once.

The code needs neither the slabs nor the raises: it just adds every deficit as it passes it.

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        ans = 0
        for i in range(1, len(nums)):
            if nums[i] < nums[i - 1]:      # this pair is out of order
                ans += nums[i - 1] - nums[i]
        return ans

Watch the full trace of example 1 — 9 steps: the rose arrow marks each out-of-order pair, the emerald suffix raise closes it, and the free carry hands the next gap to its own raise:

starttotal = 0

0123

rose arrow = the deficit of the pair under inspection · emerald flash = the suffix raise · slate = settled pair

1 / 9

comparingseenresultdiscarded

The greedy reads only the gaps between neighbors, because non-decreasing is a pairwise condition: if every pair (i-1, i) has the right value at least as tall as the left one, the whole array is sorted. Trace example 1, [3,3,2,1]. Two gaps stand out, and the badge below keeps the running total of x values spent, starting at 0.

Example 2 compresses the whole strategy into a single move: one 4-unit arrow, one suffix raise, done:

starttotal = 0

0123

rose arrow = the deficit of the pair under inspection · emerald flash = the suffix raise · slate = settled pair

1 / 5

comparingseenresultdiscarded

Second example: [5,1,2,3]. The whole problem sits at the very first pair — 5 towers over 1 by 4 units, a deficit that dwarfs every other gap on the board.

Why it is linear and optimal: one left-to-right pass with constant extra space, and the result equals the lower bound, so no algorithm can spend less. The answer fits comfortably in a 64-bit integer — at most (n − 1) · 10^9, under 10^15 — and Python absorbs that without breaking a sweat, which is why interviewers expect the sum rather than a simulation. Compare the two runs: the isolated brute force spent 3 on example 1, the greedy 2; on example 2, 9 against 4.