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.

import java.util.Arrays;

class MinimizeDifference {
    static int minimizeDifference(int[] arr, int n, int k) {
        Arrays.sort(arr);
        int minDiff = arr[n - 1] - arr[0];
        for (int i = 1; i < n; i++) {
            int minHeight = Math.min(arr[0] + k, arr[i] - k);
            int maxHeight = Math.max(arr[n - 1] - k, arr[i - 1] + k);
            minDiff = Math.min(minDiff, maxHeight - minHeight);
        }
        return minDiff;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 15, 10};
        int k = 6;
        System.out.println("Minimum difference: " + minimizeDifference(arr, arr.length, k));
    }
}
            

Output:

Minimum difference: 5

Method 2: Brute Force

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

import java.util.Arrays;

class BruteForceMinDifference {
    static int findMinDifference(int[] arr, int n, int k) {
        int minDiff = Integer.MAX_VALUE;
        for (int i = 0; i < (1 << n); i++) {
            int[] modifiedArr = new int[n];
            for (int j = 0; j < n; j++) {
                modifiedArr[j] = (i & (1 << j)) != 0 ? arr[j] + k : arr[j] - k;
            }
            int minHeight = Arrays.stream(modifiedArr).min().getAsInt();
            int maxHeight = Arrays.stream(modifiedArr).max().getAsInt();
            minDiff = Math.min(minDiff, maxHeight - minHeight);
        }
        return minDiff;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 15, 10};
        int k = 6;
        System.out.println("Minimum difference: " + findMinDifference(arr, arr.length, k));
    }
}
            

Output:

Minimum difference: 5

Method 3: Optimized Sorting Approach

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

import java.util.Arrays;

class OptimizedMinDifference {
    static int getMinimizedDifference(int[] arr, int n, int k) {
        Arrays.sort(arr);
        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 Math.min(minDiff, largest - smallest);
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 15, 10};
        int k = 6;
        System.out.println("Minimum difference: " + getMinimizedDifference(arr, arr.length, k));
    }
}
            

Output:

Minimum difference: 5