Minimise the maximum difference between heights

The problem, simply

You get the heights of n towers and a number k. Every tower must change exactly once: either grow by k or shrink by k. A tower may not end up with a negative height.

After the changes, look at the tallest and the shortest tower. Make their difference as small as possible, and give back that difference.

A story to remember it

Picture it

Examples

Way 1: the simple way

Every tower has two choices, grow or shrink. Try every mix of choices and keep the best gap. Skip any choice that makes a height negative.

class Solution {
    public int getMinDiff(int[] arr, int k) {
        return tryAll(arr, k, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
    }

    // low and high are the shortest and tallest heights chosen so far.
    private int tryAll(int[] arr, int k, int i, int low, int high) {
        if (i == arr.length) return high - low;
        int up = arr[i] + k, down = arr[i] - k;
        int best = tryAll(arr, k, i + 1, Math.min(low, up), Math.max(high, up));      // grow
        if (down >= 0) {                                                               // shrink
            best = Math.min(best, tryAll(arr, k, i + 1, Math.min(low, down), Math.max(high, down)));
        }
        return best;
    }
}

How long it takes: two choices per tower, so 2^n mixes, O(2^n). Extra room: the calls waiting on each other, one per tower, O(n).

Way 2: the clever way

Sort the towers. In the best plan, the short ones grow and the tall ones shrink. Say towers 0..i-1 grow and towers i..n-1 shrink.

1. Sort. Start with best = arr[n-1] - arr[0]. That is the plan where every tower moves the same way.
2. For each switch point i from 1 to n - 1:
   • If arr[i] - k < 0, tower i cannot shrink, so skip this switch point.
   • The shortest height is min(arr[0] + k, arr[i] - k): the smallest grower or the smallest shrinker.
   • The tallest height is max(arr[i-1] + k, arr[n-1] - k): the biggest grower or the biggest shrinker.
   • Keep the smallest tallest - shortest.

Why only the ends? Inside the growers, the smallest is arr[0] + k and the biggest is arr[i-1] + k, because sorting keeps them in order. The same holds for the shrinkers.

class Solution {
    public int getMinDiff(int[] arr, int k) {
        int n = arr.length;
        Arrays.sort(arr);
        int best = arr[n - 1] - arr[0];            // everyone moves the same way
        for (int i = 1; i < n; i++) {              // towers 0..i-1 grow, i..n-1 shrink
            if (arr[i] - k < 0) continue;          // tower i cannot shrink
            int shortest = Math.min(arr[0] + k, arr[i] - k);
            int tallest = Math.max(arr[i - 1] + k, arr[n - 1] - k);
            best = Math.min(best, tallest - shortest);
        }
        return best;
    }
}

How long it takes: sorting is O(n log n), then one walk, O(n). In total O(n log n). Extra room: a few numbers, O(1) (plus what the sort uses).

Watch out for

• Check the version you are given. In one version heights may go negative; then drop the arr[i] - k < 0 check. In this version they may not.
• Using arr[i] + k and arr[i-1] - k by mistake flips the roles. The grower at the switch is i - 1, the first shrinker is i.
• One tower: the loop never runs and the answer is 0.

What interviewers ask next

• Prove that small ones grow and big ones shrink. If a taller tower grows while a shorter one shrinks, swapping their choices never makes the spread wider. So some best plan looks like a switch point.
• What if each tower may also stay the same (choices -k, 0, +k)? The same idea works with more care, or you can sort all 3n candidate heights and use a sliding window that covers one choice of every tower.
• What if each tower has its own k? Then it becomes "pick one value from each list to make the range smallest": push all candidates into one sorted list and slide a window that touches every tower, or use a min heap over the lists.

Remember this

Grown-up words: the boxes and kneeling are +k and -k, the switch point is the partition index, trying all mixes is brute force over 2^n subsets, and sorting first then deciding is a greedy argument.