Course contentsShow
← Computer Science
Lesson 901 of 2,87221. Greedy AlgorithmsFree lesson

Minimize Maximum Difference in Heights

Minimize height difference after modifications by sorting and greedily adjusting boundary elements.

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 1 and 15

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:

  1. Increase the shortest towers by k to pull them up
  2. Decrease the tallest towers by k to pull them down
  3. 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.