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?

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

Solution 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.

Solution 3

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

Solution 4

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

View more solutions

Comments

[ChrisMM]

Some recommended reading: Why should I not #include <bits/stdc++.h>? and Why is using namespace std; considered bad practive?

[ChrisMM]

What is the problem you are having? "Can anyone help me provide the correct solution" is not a question that will be well-received on SO.

[Go Beyond]

Does this answer your question? Minimum difference between heights of Towers?

[DEEPANSHU RAWAT]

<stackoverflow.com/questions/32233916/…> This link explains it pretty well.

[Nikhil.Nixel]

Also do add the if statement to check if arr[i] is greater than k. We cant have negative heights can we?

[rahul sharma]

can u tell why it works?I did not get the intuition behind this?The code share in question is wrong although

[Himanshu Singh]

@rahulsharma I have added few more comments in the code. see if it helps. Try to dry run the code, you'll get the intuition.

[Admin]

Please add further details to expand on your answer, such as working code or documentation citations.

[Surinder]

index should start from 1 to avoid out of bound exception

[Saurabh Dhage]

Nice explaination 👍

[Embydextrous]

Great explanation!