Minimize the maximum difference between the heights

Question

Given heights of n towers and a value k. We need to either increase or decrease height of every tower by k (only once) where k > 0. The task is to minimize the difference between the heights of the longest and the shortest tower after modifications, and output this difference.

I get the intuition behind the solution but I can not comment on the correctness of the solution below.

// C++ program to find the minimum possible 
// difference between maximum and minimum 
// elements when we have to add/subtract 
// every number by k 
#include <bits/stdc++.h> 
using namespace std; 
  
// Modifies the array by subtracting/adding 
// k to every element such that the difference 
// between maximum and minimum is minimized 
int getMinDiff(int arr[], int n, int k) 
{ 
    if (n == 1) 
       return 0; 
  
    // Sort all elements 
    sort(arr, arr+n); 
  
    // Initialize result 
    int ans = arr[n-1] - arr[0]; 
  
    // Handle corner elements 
    int small = arr[0] + k; 
    int big = arr[n-1] - k; 
    if (small > big) 
       swap(small, big); 
  
    // Traverse middle elements 
    for (int i = 1; i < n-1; i ++) 
    { 
        int subtract = arr[i] - k; 
        int add = arr[i] + k; 
  
        // If both subtraction and addition 
        // do not change diff 
        if (subtract >= small || add <= big) 
            continue; 
  
        // Either subtraction causes a smaller 
        // number or addition causes a greater 
        // number. Update small or big using 
        // greedy approach (If big - subtract 
        // causes smaller diff, update small 
        // Else update big) 
        if (big - subtract <= add - small) 
            small = subtract; 
        else
            big = add; 
    } 
  
    return  min(ans, big - small); 
} 
  
// Driver function to test the above function 
int main() 
{ 
    int arr[] = {4, 6}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int k = 10; 
    cout << "\nMaximum difference is "
        << getMinDiff(arr, n, k); 
    return 0; 
} 

Can anyone help me provide the correct solution to this problem?

Answer 1

The codes above work, however I don't find much explanation so I'll try to add some in order to help develop intuition.

For any given tower, you have two choices, you can either increase its height or decrease it.
Now if you decide to increase its height from say H_i to H_i + K, then you can also increase the height of all shorter towers as that won't affect the maximum.
Similarly, if you decide to decrease the height of a tower from H_i to H_i − K, then you can also decrease the heights of all taller towers.
We will make use of this, we have n buildings, and we'll try to make each of the building the highest and see making which building the highest gives us the least range of heights(which is our answer).
Let me explain:

So what we want to do is -
1) We first sort the array(you will soon see why).

2) Then for every building from i = 0 to n-2^[1] , we try make it the highest (by adding K to the building, adding K to the buildings on its left and subtracting K from the buildings on its right).

So say we're at building H_i, we've added K to it and the buildings before it and subtracted K from the buildings after it.

So the minimum height of the buildings will now be min(H₀ + K, H_i+1 - K),
i.e. min(1st building + K, next building on right - K).

(Note: This is because we sorted the array. Convince yourself by taking a few examples.)

Likewise, the maximum height of the buildings will be max(H_i + K, H_n-1 - K),
i.e. max(current building + K, last building on right - K).

3) max - min gives you the range.

^[1]Note that when i = n-1. In this case, there is no building after the current building, so we're adding K to every building, so the range will merely be height[n-1] - height[0] since K is added to everything, so it cancels out.

Here's a Java implementation based on the idea above:

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;
    }
}

Answer 2

int getMinDiff(int a[], int n, int k) {
        sort(a,a+n); 
        int i,mx,mn,ans;
        ans = a[n-1]-a[0];  // this can be one possible solution
        
        for(i=0;i<n;i++)
        {
            if(a[i]>=k)  // since height of tower can't be -ve so taking only +ve heights
            {
                mn = min(a[0]+k, a[i]-k);
                mx = max(a[n-1]-k, a[i-1]+k);
                ans = min(ans, mx-mn);
            }
        }
        return ans;
    }

This is C++ code, it passed all the test cases.