Minimize the maximum difference between the heights

Problem Statement

You are given some heights of n towers and a number k. We can either increase the height of the tower by k or decrease the height by k, but just for once. The problem statement asks to minimize the maximum difference between the heights. That is to find out the minimum difference between the heights of the towers (longest height-smallest height) after the modification we have done.

Example

arr[] = {7,12,3}

k=8

9

Explanation: Change 7 to 15, 12 to 20, and 3 to 11 the maximum difference will be 9 and can’t be lower than that.

arr[] = {1,5,15,10}

k=3

8

Explanation: New modified array is  arr[] = {4,8,12,7}. Maximum difference will be 8.

Algorithm to minimize the maximum difference between the heights

1. Sort the given array.
2. Set the diff to the difference between the least element of the array and the first element of an array.
3. Set minimum to the first element of array + k and maximum to last element - k of the array.
4. Traverse the array from i=1 to i<n-1(one less than the length of the array).
  1. Set difference to arr[i]-k.
  2. Set sum to arr[i]+k.
  3. Check if the difference is greater than equal to minimum or sum is less than or equal to maximum.
    1. If true, then continue and skip this traversal.
  4. Check if maximum-difference is less than or equal to sum-minimum.
    1. If true, then update minimum to difference.
  5. Else set the maximum to sum.
5. Return the minimum between the diff and maximum-minimum.

Explanation

We have given a height of n towers. We have to find the minimize the maximum difference between the heights. So we can do both here and check the suitable one from either of them. But before that, we have to set some conditions as well as like if the length of an array is 1, so it not possible to calculate the minimum difference because there is only one value in a given array, so we just return 0.

We are going to sort the array if there is not a sorted array, we just sort it. We have to solve for the minimum difference between the greatest height and smallest height within an array.  So we set the value of maximum to k more than the first element and minimum to k less than the last element of an array. These values act as a helping variable for us and set temp to 0. And we will check if the minimum value we just updated is greater than the maximum, so we will just swap it.

Now we will traverse the array up to the second last element and set the difference to current array value minus k (arr[i] – k) and sum to the addition of arr[i] and k. We are going to check if the difference we now get is bigger or smaller than the difference between the currently updated value. We will update it according to the given condition and continue this till we have the smaller and bigger difference between the maximum and minimum we created. Then we just return the smaller between the diff and maximum-minimum. This is how we minimize the maximum difference between the heights.

Code to minimize the maximum difference between the heights problem

C++ code

#include<iostream>
#include<algorithm>

using namespace std;

int getMinimizeHeights(int arr[], int n, int k)
{
    if (n == 1)
        return 0;

    sort(arr, arr+n);

    int diff = arr[n-1] - arr[0];

    int minimum = arr[0] + k;
    int maximum = arr[n-1] - k;
    int temp = 0;

    if (minimum > maximum)
    {
        temp = minimum;
        minimum = maximum;
        maximum = temp;
    }
    for (int i = 1; i < n-1; i ++)
    {
        int difference = arr[i] - k;
        int sum = arr[i] + k;
        if (difference >= minimum || sum <= maximum)
            continue;

        if (maximum - difference <= sum - minimum)
            minimum = difference;
        else
            maximum = sum;
    }
    return min(diff, maximum - minimum);
}
int main()
{
    int arr[] = {7,12,3};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 8;
    cout << getMinimizeHeights(arr, n, k);
    return 0;
}

9

Java Code

import java.util.*;
import java.lang.*;
import java.io.*;
 
class MinimizeHeights
{
    public static int getMinimizeHeights(int arr[], int n, int k)
    {
        if (n == 1)
            return 0;
        Arrays.sort(arr);
        int diff = arr[n-1] - arr[0];
        int minimum = arr[0] + k;
        int maximum = arr[n-1] - k;
        int temp = 0;
        if (minimum > maximum)
        {
            temp = minimum;
            minimum = maximum;
            maximum = temp;
        }
        for (int i = 1; i < n-1; i ++)
        {
            int difference = arr[i] - k;
            int sum = arr[i] + k;
            if (difference >= minimum || sum <= maximum)
                continue;
            if (maximum - difference <= sum - minimum)
                minimum = difference;
            else
                maximum = sum;
        }
        return Math.min(diff, maximum - minimum);
    }
    public static void main(String[] args)
    {
        int arr[] = {7, 12, 3};
        int n = arr.length;
        int k = 8;
        System.out.println(getMinimizeHeights(arr, n, k));
    }
}

9

Complexity Analysis

Time Complexity for minimize the maximum difference between the heights problem

O(n Log n)  where “n” is the number of elements in the array. So minimize the maximum difference between the heights problem has time complexity similar to that of merge sort.

Space Complexity for minimize the maximum difference between the heights problem

O(n)  where “n” is the number of elements in the array. So minimize the maximum difference between the heights problem has linear space complexity.