Minimize Maximum Difference in Heights
You'll learn how to reduce variation in an array by making greedy boundary adjustments after sorting.
The Core Problem
Imagine you have n towers with different heights. You can increase or decrease each tower's height by at most k units (but you must modify every tower). Your goal: minimize the maximum difference between the tallest and shortest towers after all adjustments.
This is a classic greedy optimization problem where order matters tremendously.
Why Sorting Comes First
Before making any decisions, sort the heights. Why? Because once sorted, the minimum and maximum values are at the boundaries, making it easier to reason about optimal adjustments.
Consider heights [1, 10, 15] with k = 6:
- Unsorted, it's chaotic to track all possible min/max combinations
- Sorted, you know the extremes are
1and15
The Greedy Strategy
After sorting, the key insight: the new minimum will either be the smallest tower increased by k, or some tower decreased by k. Similarly for the maximum.
Greedily adjust:
- Increase the shortest towers by
kto pull them up - Decrease the tallest towers by
kto pull them down - Check each possible "split point" where towers before it are increased and towers after are decreased
For each split, calculate the resulting max difference. The answer is the minimum across all valid configurations.
Why This Works
The greedy choice (sorting + boundary manipulation) works because you're systematically exploring where the "transition" from increasing to decreasing happens. You never need to consider mixed strategies on interior elements—the extremes dictate the optimal solution.
Key Takeaway:
Sort first, then greedily test boundary adjustments at each split point to minimize the maximum height difference efficiently.