Minimize the Heights II

Minimize the Heights II is a classic greedy array problem. Every tower must change by exactly k — you choose to either raise it or lower it — and you want the final array as flat as possible. The win comes from one observation: after sorting, the best plan is always "raise a prefix, lower the rest."

The slow way first

Each tower independently goes up or down, so there are 2^n combinations of choices. Trying them all is O(2ⁿ) — hopeless for anything but a tiny array. We need structure.

The question to ask: if I knew which towers go up and which go down, would the assignment be arbitrary? It is not. Once the array is sorted, raising a short tower and lowering a tall one is what flattens the array. Raising a tall tower or lowering a short one only makes the spread worse.

The idea: sort, then split

Sort the array. Now imagine a split point i: every height in a[0..i] goes up by k, and every height in a[i+1..] goes down by k. Because the array was sorted, only two values can be the new tallest and only two can be the new shortest:

• new tallest = max(a[i] + k, a[n-1] - k)
• new shortest = min(a[0] + k, a[i+1] - k)

Sweep i across every split, recompute that candidate spread, and keep the smallest one. Start the answer at the unmodified spread a[n-1] - a[0] so the "raise everything or lower everything" plan is covered too.

The key insight: sorting collapses 2^n choices into just n meaningful split points, because the four numbers that can be the new extremes are always the same handful of endpoints.

Walk through it

Step through the animation. The array is sorted to [1, 5, 8, 10] and k = 2. The pointer i marks the split. Boxes left of (and including) i are "raised"; the rest are "lowered." For each split we read off big and small, form the candidate spread, and shrink the running answer. The smallest spread we ever see is 5.

Pseudocode

sort a
ans = a[last] - a[first]               # baseline: no useful split
for each split index i from 0 to n-2:
    big   = max(a[i] + k, a[last] - k) # tallest after raising left, lowering right
    small = min(a[first] + k, a[i+1] - k)   # shortest after the same split
    ans   = min(ans, big - small)      # keep the flattest result so far
return ans

The Python solution

def get_min_diff(a, k):
    a.sort()
    n = len(a)
    ans = a[n - 1] - a[0]
    for i in range(n - 1):
        big = max(a[i] + k, a[n - 1] - k)
        small = min(a[0] + k, a[i + 1] - k)
        ans = min(ans, big - small)
    return ans

• a.sort() is what makes the prefix/suffix split valid — without it the endpoints mean nothing.
• ans = a[n - 1] - a[0] seeds the answer with the do-nothing-useful spread.
• The loop runs i from 0 to n - 2, so a[i + 1] is always in bounds.
• Line 6 picks the tallest after the split: either the raised a[i] or the lowered a[n - 1].
• Line 7 picks the shortest: either the raised a[0] or the lowered a[i + 1].
• Line 8 keeps the smallest spread seen so far. After the sweep, ans is the answer.

Complexity

Sorting costs O(n log n) and the sweep is O(n), so the sort dominates. We use only a few scalar variables, so extra space is O(1) (ignoring the sort).

When this pattern shows up

Practice