Minimize the Heights I

JavaView on GFG

Intuition

Minimize difference between max and min tower heights by adding or subtracting k exactly once from each.

Algorithm

1Sort. For each split point: left towers get +k, right towers get -k. New range = max(arr[i-1]+k, arr[n-1]-k) - min(arr[0]+k, arr[i]-k).

Common Pitfalls

•Sort, try each split. Must add OR subtract exactly k (not choosing per tower). Check all n split points.

Minimize the Heights I.java

Java

// Approach: Sort. Try decrease each by k and increase others by k. Track min of max-min across splits.
// Time: O(n log n) Space: O(1)
class Solution {
    public int getMinDiff(int k, int[] arr) {
        int n = arr.length;
        if (n == 1) {
            return 0; // Single tower, no difference
        }

        // Sort the array
        Arrays.sort(arr);

        // Initial difference
        int initialDiff = arr[n - 1] - arr[0];
        int minDiff = initialDiff;

        // Base heights after adding/subtracting k
        int smallest = arr[0] + k;
        int largest = arr[n - 1] - k;

        // Traverse through the sorted array
        for (int i = 1; i < n; i++) {
            int minHeight = Math.min(smallest, arr[i] - k);
            int maxHeight = Math.max(largest, arr[i - 1] + k);
            minDiff = Math.min(minDiff, maxHeight - minHeight);
        }

        return minDiff;
    }
}

Was this solution helpful?