Minimum Increments to Make Array Non-Increasing

Minimum Increments to Make Array Non-Increasing is a clean greedy warm-up. The twist is that you may only add to elements, never subtract — so the direction you sweep the array decides everything.

The slow way first

You might try to search for the best final array — what value should each position end at? That space is enormous, and brute-forcing combinations is hopelessly slow.

The question to ask: since I can only raise values, when is a position actually forced to change? A position a[i] is only a problem if it is smaller than its right neighbour a[i + 1]. If so, the only legal fix is to raise a[i] up to a[i + 1]. That single observation removes all the searching.

The idea: sweep right to left

Walk the array from the second-to-last element down to the first. At each i, compare with the already-finalized a[i + 1]. If a[i] < a[i + 1], you are forced to add a[i + 1] - a[i] operations and set a[i] = a[i + 1]. Accumulate every such difference into ops.

Going right to left matters: the right neighbour is already finalized before we look at the current element, so we never have to revisit a decision. Raising a[i] to exactly a[i + 1] is the cheapest legal move — anything higher wastes operations, anything lower is still a violation.

Walk through it

Step through the animation. The pointer i moves right to left. At each stop we compare the current cell with the one to its right; if it is smaller we raise it and grow ops. By the end the array is [4, 4, 4, 4] and ops = 6.

Pseudocode

ops = 0
for i from len(a) - 2 down to 0:
    if a[i] < a[i + 1]:
        ops += a[i + 1] - a[i]    # forced increments
        a[i] = a[i + 1]           # raise to the right neighbour
return ops

The Python solution

def min_increments(a):
    ops = 0
    for i in range(len(a) - 2, -1, -1):
        if a[i] < a[i + 1]:
            ops += a[i + 1] - a[i]
            a[i] = a[i + 1]
    return ops

• ops accumulates the total number of increments we are forced to make.
• The loop runs i from len(a) - 2 down to 0, always comparing against the already-fixed right neighbour.
• if a[i] < a[i + 1] is the only condition that costs anything — a non-increasing pair is free.
• ops += a[i + 1] - a[i] pays exactly the gap, the minimum to remove the violation.
• a[i] = a[i + 1] raises the current element so later comparisons see its new value.

Complexity

We touch each element once and only track a running counter, so it is O(n) time and O(1) extra space. The greedy move — fix each violation locally by raising to the right neighbour — is provably optimal because that increment is unavoidable.

When this pattern shows up

Practice