Minimum difference between heights of Towers?

Question

I was going through some interview questions, I saw this one

You are given the height of n towers and value k. You have to either increase or decrease the height of every tower by k. You need to minimize the difference between the height of the longest and the shortest tower and output this difference.

I think the answer will be (maxheight-k) - (minheight + k). I have tried on some test cases it is running fine.

But I am not sure, I think I am missing something, Am I ?

Answer 1

m7thon's answer explains the problem with your solution, so I'll just explain how you can actually solve this . . .

The big thing to observe is that for any given tower, if you choose to increase its height from h_i to h_i + k, then you might as well increase the height of all shorter towers: that won't affect the maximum (because if h_j < h_i, then h_j + k < h_i + k), and may help by increasing the minimum. Conversely, if you choose to decrease the height of a tower from h_i to h_i − k, then you might as well decrease the heights of all taller towers.

So while there are 2ⁿ possible ways to choose which towers should be increased vs. decreased, we can actually ignore most of these. Some tower will be the tallest tower that we increase the height of; for all shorter towers, we will increase their height as well, and for all taller towers, we will decrease their height. So there are only n interesting ways to choose which towers should be increased vs. decreased: one for each tower's chance to be the tallest tower that we increase the height of.

[Pedantic note #1: You may notice that it's also valid to decrease the heights of all towers, in which case there's no such tower. But that's equivalent to increasing the heights of all towers — whether we add k to every height or subtract k from every height, either way we're not actually changing the max-minus-min.]

[Pedantic note #2: I've only mentioned "shorter towers" and "taller towers", but it's also possible that multiple towers have the same initial height. But this case isn't really important, because we might as well increase them all or decrease them all — there's no point increasing some and decreasing others. So the approach described here still works fine.]

So, let's start by sorting the original heights and numbering them in increasing order, so that h₁ is the original height of the originally-shortest tower and h_n is the original height of the originally-tallest tower.

For each i, try the possibility that the ith-shortest tower is the tallest tower that we increase the height of; that is, try the possibility that we increase h₁ through h_i and decrease h_i+1 through h_n. There are two groups of cases:

• If i < n, then the final height of the finally-shortest tower is min(h₁ + k, h_i+1 − k), and the final height of the finally-tallest tower is max(h_i + k, h_n − k). The final difference in this case is the latter minus the former.
• If i = n, then we've increased the heights of all towers equally, so the final difference is just h_n − h₁.

We then take the least difference from all n of these possibilities.

Here's a Java method that implements this (assuming int-valued heights; note that h_i is arr[i-1] and h_i+1 is arr[i]):

private static int doIt(final int[] arr, final int k) {
    java.util.Arrays.sort(arr);
    final int n = arr.length;
    int result = arr[n - 1] - arr[0];
    for (int i = 1; i < n; ++i) {
        final int min = Math.min(arr[0] + k, arr[i] - k);
        final int max = Math.max(arr[n - 1] - k, arr[i - 1] + k);
        result = Math.min(result, max - min);
    }
    return result;
}

Note that I've pulled the i = n case before the loop, for convenience.

Answer 2

Lets say you have three towers of heights 1, 4 and 7, and k = 3. According to your reasoning the optimal minimum difference is (7 - 3) - (1 + 3) = 0. But what do you do with the tower of height 4? You either need to increase or decrease this, so the minimum difference you can achieve is in fact 3 in this example.

Even if you are allowed to keep a tower at its height, then the example 1, 5, 7 will disprove your hypothesis.

I know this does not solve the actual minimization problem, but it does show that it is not as simple as you thought. I hope this answers your question "Am I missing something?".

Answer 3

I assume this came from gfg.

The answer of @ruakh is perhaps the best I've found online, it'll work for most cases, but for the practice problem on gfg, there are a few cases which can cause the minimum to go below 0, and the question doesn't allow any height to be < 0.

So for that, you'll need an additional check, and the rest of it is pretty much entirely inspired from ruakh's answer

class Solution {
    int getMinDiff(int[] arr, int n, int k) {
        Arrays.sort(arr);
        int ans = arr[n-1] - arr[0];
        int smallest = arr[0] + k, largest = arr[n-1]-k;
        for(int i = 0; i < n-1; i++){
            int min = Math.min(smallest, arr[i+1]-k);
            int max = Math.max(largest, arr[i]+k);
            if(min < 0) continue;
            ans = Math.min(ans, max-min);
        }
        return ans;
    }
}

I also went in for 0-based indexing for the heights to make it more obvious, but maybe that's subjective.

Edit: One case where the < 0 check is important, is when the array is 8 1 5 4 7 5 7 9 4 6 and k is 5. The expected answer for this is 8, without the < 0 check, you'd get 7.