Minimize the Heights II Geek For Geeks Medium Problem Solution

Photo by Алекс Арцибашев on Unsplash

Given an array arr[] denoting heights of N towers and a positive integer K.

For each tower, you must perform exactly one of the following operations exactly once.

• Increase the height of the tower by K
• Decrease the height of the tower by K

Find out the minimum possible difference between the height of the shortest and tallest towers after you have modified each tower.

You can find a slight modification of the problem here.
Note: It is compulsory to increase or decrease the height by K for each tower. After the operation, the resultant array should not contain any negative integers.

Example 1:

Input:
K = 2, N = 4
Arr[] = {1, 5, 8, 10}
Output:
5
Explanation:
The array can be modified as 
{1+k, 5-k, 8-k, 10-k} = {3, 3, 6, 8}. 
The difference between 
the largest and the smallest is 8-3 = 5.

Example 2:

Input:
K = 3, N = 5
Arr[] = {3, 9, 12, 16, 20}
Output:
11
Explanation:
The array can be modified as
{3+k, 9+k, 12-k, 16-k, 20-k} -> {6, 12, 9, 13, 17}. 
The difference between 
the largest and the smallest is 17-6 = 11.

Your Task:
You don’t need to read input or print anything. Your task is to complete the function getMinDiff() which takes the arr[], n, and k as input parameters and returns an integer denoting the minimum difference.

Approach

This approach involves sorting the array initially. Then, for each tower starting from the second one, we calculate the potential heights after modifying it (either increasing or decreasing by K). We consider two scenarios:

1. If the tower’s height minus K is negative, we continue to the next tower since we cannot have negative heights.
2. Otherwise, we calculate the potential minimum and maximum heights after modification based on the current tower.

We keep track of the minimum difference between the potential maximum and minimum heights among all towers.

Here’s a step-by-step explanation:

1. Sort the array to get the heights in ascending order.
2. Initialize the minimum difference variable to the difference between the last and first towers in the sorted array.
3. Iterate through the array starting from the second tower:

• If the tower’s height minus K is negative, continue to the next tower.
• Calculate the potential minimum and maximum heights after modification based on the current tower.
• Update the minimum difference if the potential difference is smaller.

1. Return the minimum difference.

The idea is to find the optimal modification for each tower that minimizes the overall difference between the tallest and shortest towers in the array.

let’s take the first example to illustrate the approach.

Example 1:

Input:
K = 2, N = 4
Arr[] = {1, 5, 8, 10}

1. Sort the array:

• Sorted Arr[] = {1, 5, 8, 10}

1. Initialize minimum difference:

• Minimum difference = 10 - 1 = 9

1. Iterate through the array starting from the second tower (5):

• For the second tower (5 — K), skip it since it would be negative.
• For the third tower (8):

If we decrease by K, potential minimum = 8 - K = 6 
If we increase by K, potential maximum = 8 + K = 10 
Potential difference = 10 - 6 = 4 Update minimum difference to 4

• For the fourth tower (10):

If we decrease by K, potential minimum = 10 - K = 8 
If we increase by K, potential maximum = 10 + K = 12 
Potential difference = 12 - 8 = 4 Update minimum difference to 4

1. Final minimum difference:

• Minimum difference = 4

So, for this example, the minimum possible difference between the height of the shortest and tallest towers after modification is 4.

C++ Code

//{ Driver Code Starts
// Initial template for C++

#include <bits/stdc++.h>
using namespace std;

// } Driver Code Ends
// User function template for C++

class Solution {
  public:
    int getMinDiff(int arr[], int n, int k) {
        // code here
        sort(arr,arr+n);
        
        int minimum = arr[n-1] - arr[0];
        
        for(int i=1; i<n;i++){
            if(arr[i]- k < 0){
                continue;
            }
            minimum = min(minimum, max(arr[n-1] - k, arr[i-1]+k) - min(arr[0]+k, arr[i]-k));
        }
        
        return minimum;
    }
};

//{ Driver Code Starts.
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> k;
        cin >> n;
        int arr[n];
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        Solution ob;
        auto ans = ob.getMinDiff(arr, n, k);
        cout << ans << "\n";
    }
    return 0;
}
// } Driver Code Ends

Thank you for reading….😃