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 <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int minimizeDifference(int arr[], int n, int k) {
    qsort(arr, n, sizeof(arr[0]), compare);
    int minDiff = arr[n - 1] - arr[0];
    for (int i = 1; i < n; i++) {
        int minHeight = (arr[0] + k < arr[i] - k) ? arr[0] + k : arr[i] - k;
        int maxHeight = (arr[n - 1] - k > arr[i - 1] + k) ? arr[n - 1] - k : arr[i - 1] + k;
        minDiff = (minDiff < maxHeight - minHeight) ? minDiff : maxHeight - minHeight;
    }
    return minDiff;
}

int main() {
    int arr[] = {1, 15, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 6;
    printf("Minimum difference: %d", 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 <stdio.h>
#include <limits.h>

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++) {
            if (i & (1 << j))
                modifiedArr[j] = arr[j] + k;
            else
                modifiedArr[j] = arr[j] - k;
        }
        int minHeight = modifiedArr[0], maxHeight = modifiedArr[0];
        for (int j = 1; j < n; j++) {
            if (modifiedArr[j] < minHeight) minHeight = modifiedArr[j];
            if (modifiedArr[j] > maxHeight) maxHeight = modifiedArr[j];
        }
        int diff = maxHeight - minHeight;
        if (diff < minDiff) minDiff = diff;
    }
    return minDiff;
}

int main() {
    int arr[] = {1, 15, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 6;
    printf("Minimum difference: %d", 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 <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int getMinimizedDifference(int arr[], int n, int k) {
    qsort(arr, n, sizeof(arr[0]), compare);
    int minDiff = arr[n - 1] - arr[0];
    int smallest = arr[0] + k, largest = arr[n - 1] - k;
    if (smallest > largest) {
        int temp = smallest;
        smallest = largest;
        largest = temp;
    }
    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 (largest - smallest < minDiff) ? largest - smallest : minDiff;
}

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

Output:

Minimum difference: 5