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 to 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

class Solution:
    def getMinDiff(self, arr, n, k):
        # code here
        arr.sort()
        res = arr[-1]-arr[0]
        
        for i in range(1, n):
            if arr[i]>=k:
                # at a time we can increase or decrease one number only. 
                # Hence assuming we decrease ith elem, we will increase i-1 th elem.
                # using this we basically find which is new_min and new_max possible 
                # and if the difference is smaller than res, we return the same. 
                new_min = min(arr[0]+k, arr[i]-k)
                new_max = max(arr[-1]-k, arr[i-1]+k)
                res = min(res, new_max-new_min)
        
        return res

Answer 3

class Solution {
  public:
    int getMinDiff(int arr[], int n, int k) {
            sort(arr, arr+n);
        int diff = arr[n-1]-arr[0];
        int mine, maxe;
        for(int i = 0; i < n; i++)
            arr[i]+=k;
        mine = arr[0];
        maxe = arr[n-1]-2*k;
        for(int i = n-1; i > 0; i--){
            if(arr[i]-2*k < 0)
                break;
            mine = min(mine, arr[i]-2*k);
            maxe =  max(arr[i-1], arr[n-1]-2*k);
            diff = min(diff, maxe-mine);
        }
        return diff;
    }
};

Answer 4

Here is the C++ code, I have continued from where you left. The code is self-explanatory.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minDiff(int arr[], int n, int k)
{
    // If the array has only one element.
    if (n == 1)
    {
        return 0;
    }
    //sort all elements
    sort(arr, arr + n);

    //initialise 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 the elements to keep the array sorted.
        int temp = small;
        small = big;
        big = temp;
    }

    //traverse middle elements
    for (int i = 0; i < n - 1; i++)
    {
        int subtract = arr[i] - k;
        int add = arr[i] + k;

        // If both subtraction and addition do not change the diff.
        // Subtraction does not give new minimum.
        // Addition does not give new maximum.
        if (subtract >= small or 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);
}

int main(void)
{
    int arr[] = {1, 5, 15, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "\nMaximum difference is: " << minDiff(arr, n, k) << endl;
    return 0;
}

Answer 5

Here's a solution:-

But before jumping on to the solution, here's some info that is required to understand it. In the best case scenario, the minimum difference would be zero. This could happen only in two cases - (1) the array contain duplicates or (2) for an element, lets say 'x', there exists another element in the array which has the value 'x + 2*k'.

The idea is pretty simple.

1. First we would sort the array.
2. Next, we will try to find either the optimum value (for which the answer would come out to be zero) or at least the closest number to the optimum value using Binary Search

Here's a Javascript implementation of the algorithm:-

function minDiffTower(arr, k) {
    arr = arr.sort((a,b) => a-b);
    let minDiff = Infinity;
    let prev = null;

    for (let i=0; i<arr.length; i++) {
        let el = arr[i];
        
        // Handling case when the array have duplicates
        if (el == prev) {
            minDiff = 0;
            break;
        }
        prev = el;

        let targetNum = el + 2*k; // Lets say we have an element 10. The difference would be zero when there exists an element with value 10+2*k (this is the 'optimum value' as discussed in the explaination
        let closestMatchDiff =  Infinity; // It's not necessary that there would exist 'targetNum' in the array, so we try to find the closest to this number using Binary Search
        let lb = i+1;
        let ub = arr.length-1;
        while (lb<=ub) {
            let mid = lb + ((ub-lb)>>1);
            let currMidDiff =  arr[mid] > targetNum ? arr[mid] - targetNum : targetNum - arr[mid];
            closestMatchDiff = Math.min(closestMatchDiff, currMidDiff); 
            if (arr[mid] == targetNum) break; // in this case the answer would be simply zero, no need to proceed further
            else if (arr[mid] < targetNum) lb = mid+1;
            else ub = mid-1;
        }
        minDiff = Math.min(minDiff, closestMatchDiff);
    }
    return minDiff;
}

Answer 6

This python code might be of some help to you. Code is self explanatory.

def getMinDiff(arr, n, k):
    arr = sorted(arr)
    ans = arr[-1]-arr[0] #this case occurs when either we subtract k or add k to all elements of the array
    for i in range(n):
        mn=min(arr[0]+k, arr[i]-k) #after sorting, arr[0] is minimum. so adding k pushes it towards maximum. We subtract k from arr[i] to get any other worse (smaller) minimum. worse means increasing the diff b/w mn and mx
        mx=max(arr[n-1]-k, arr[i]+k) # after sorting, arr[n-1] is maximum. so subtracting k pushes it towards minimum. We add k to arr[i] to get any other worse (bigger) maximum. worse means increasing the diff b/w mn and mx
        ans = min(ans, mx-mn)
    return ans

Answer 7

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.