Minimize Maximum Height Difference is a classic greedy problem. You are given tower heights and a fixed amount k. You must change every tower by exactly +k or -k, then make the gap between the tallest and shortest tower as small as possible.
Problem. Given an array a of n heights and an integer k, you must add k to or subtract k
from every element. Return the minimum possible difference between the largest and smallest height
after the changes.
Example: a = [1, 5, 8, 10], k = 2 → answer 5. (Raise 1 and 5, lower 8 and 10:
heights become [3, 7, 6, 8], range 8 - 3 = 5.)
The slow way first
There are two choices per tower, so brute force tries all 2ⁿ combinations of +k/-k and takes the best range. That is exponential — hopeless for more than a couple dozen towers.
The question to ask: is there structure that tells me which towers should go up and which should go down? There is — and it appears the moment we sort.
The idea: sort, then pick one split
After sorting, the smart move is monotonic: smaller towers go up (+k), larger towers go down (-k). So the only real decision is where the boundary between "up" and "down" sits. Try every split point i: towers a[0..i] go up, towers a[i+1..n-1] go down. For each split, the new smallest height is min(a[0]+k, a[i+1]-k) and the new largest is max(a[i]+k, a[n-1]-k). Track the smallest range over all splits.
The key insight: only the boundary elements matter. The smallest candidate is either a[0]+k or a[i+1]-k; the largest is either a[i]+k or a[n-1]-k. Everything in between is squeezed inside that range.
Walk through it
Step through the animation. The array [1, 5, 8, 10] is sorted, and the split i pointer sweeps left to right. At each split we raise the cells up to i and lower the rest, then read off small and big. The best range starts at 9 (the untouched gap) and drops to 5 at the first split, where it stays.
Pseudocode
sort a ascending
best = a[last] - a[first] # baseline: change nothing useful
for each split point i from 0 to n-2:
small = min(a[first] + k, a[i+1] - k) # raise low side, lower high side
big = max(a[i] + k, a[last] - k)
best = min(best, big - small)
return bestThe Python solution
def min_height_diff(a, k):
a.sort()
best = a[-1] - a[0]
for i in range(len(a) - 1):
small = min(a[0] + k, a[i + 1] - k)
big = max(a[i] + k, a[-1] - k)
best = min(best, big - small)
return besta.sort()makes the up/down decision monotonic — low towers up, high towers down.best = a[-1] - a[0]is the baseline range before we commit to any split.- The loop tries each split point
i: elementsa[0..i]go up,a[i+1..]go down. smallis the new minimum: either the lowest raised towera[0]+kor the lowest lowered towera[i+1]-k.bigis the new maximum: either the highest raised towera[i]+kor the highest lowered towera[-1]-k.- We keep the smallest
big - smallseen across all splits.
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force (all signs) | O(2ⁿ) (moderate) | every +k/-k combination |
| Sort + single sweep | O(n log n) (moderate) | sort dominates the linear sweep |
O(1) (fast)The sort costs O(n log n) and the sweep is a single O(n) pass, so sorting dominates. We use only a few scalar variables, so the extra space is O(1).
When this pattern shows up
When a problem lets you nudge each element by a fixed amount and asks to minimize a spread, sort first. Sorting usually turns a tangle of independent choices into one monotonic decision — here, a single split point you can sweep in linear time.
Do not blindly assume the answer is (a[-1] - a[0]) - 2k. That is only valid when every split improves
things; sometimes raising a low tower past a lowered high tower makes the range worse, so you must still
compare against the baseline and take the minimum over all splits.
Practice
For a = [1, 5, 8, 10], k = 2, at split i = 2 (raise 1, 5, 8; lower 10), what are small, big, and the range?
1. Why do we sort the array first?
2. At each split point i, what is the candidate minimum height?
3. Why must we still compare each split against the baseline range?
4. What is the overall time complexity?