Minimize the Maximum Difference Between Heights

Understanding the Problem

The goal is to minimize the maximum difference between the heights of towers after modifying them within a given range.

Method 1: Sorting and Greedy Approach

This method sorts the array and then modifies heights by either increasing or decreasing within the given range.

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

int minimizeDifference(int arr[], int n, int k) {
    sort(arr, arr + n);
    int minDiff = arr[n - 1] - arr[0];
    for (int i = 1; i < n; i++) {
        int minHeight = min(arr[0] + k, arr[i] - k);
        int maxHeight = max(arr[n - 1] - k, arr[i - 1] + k);
        minDiff = min(minDiff, maxHeight - minHeight);
    }
    return minDiff;
}

int main() {
    int arr[] = {1, 15, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 6;
    cout << "Minimum difference: " << minimizeDifference(arr, n, k);
    return 0;
}
            

Output:

Minimum difference: 5

Method 2: Brute Force

This method tries all possibilities of adding or subtracting k from each element.

#include <iostream>
#include <climits>
using namespace std;

int findMinDifference(int arr[], int n, int k) {
    int minDiff = INT_MAX;
    for (int i = 0; i < (1 << n); i++) {
        int modifiedArr[n];
        for (int j = 0; j < n; j++) {
            modifiedArr[j] = (i & (1 << j)) ? arr[j] + k : arr[j] - k;
        }
        int minHeight = *min_element(modifiedArr, modifiedArr + n);
        int maxHeight = *max_element(modifiedArr, modifiedArr + n);
        minDiff = min(minDiff, maxHeight - minHeight);
    }
    return minDiff;
}

int main() {
    int arr[] = {1, 15, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 6;
    cout << "Minimum difference: " << findMinDifference(arr, n, k);
    return 0;
}
            

Output:

Minimum difference: 5

Method 3: Optimized Sorting Approach

An optimized approach that modifies heights while iterating through the sorted array.

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

int getMinimizedDifference(int arr[], int n, int k) {
    sort(arr, arr + n);
    int minDiff = arr[n - 1] - arr[0];
    int smallest = arr[0] + k, largest = arr[n - 1] - k;
    if (smallest > largest) swap(smallest, largest);
    for (int i = 1; i < n - 1; i++) {
        int decrease = arr[i] - k;
        int increase = arr[i] + k;
        if (decrease >= smallest || increase <= largest) continue;
        if (largest - decrease <= increase - smallest)
            smallest = decrease;
        else
            largest = increase;
    }
    return min(minDiff, largest - smallest);
}

int main() {
    int arr[] = {1, 15, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 6;
    cout << "Minimum difference: " << getMinimizedDifference(arr, n, k);
    return 0;
}
            

Output:

Minimum difference: 5