Minimize the Heights II

JavaView on GFG

Intuition

Same as minimize-the-heights-i but can choose to add OR subtract k for each tower independently.

Algorithm

1Sort. For each index i: left half gets +k, right half gets -k (or some combination). Try all splits.

Common Pitfalls

•Sort, iterate split points. At split i: minVal=min(arr[0]+k, arr[i]-k), maxVal=max(arr[i-1]+k, arr[n-1]-k). Track minimum range.

Minimize the Heights II.java

Java

// Approach: Sort. For each split point: max of (arr[0]+k, arr[i]+k) and min of (arr[n-1]-k, arr[i+1]-k).
// Time: O(n log n) Space: O(1)
import java.util.*;

class Solution {
    int getMinDiff(int[] arr, int k) {
        Arrays.sort(arr);

        int n = arr.length;
        int ans = arr[n - 1] - arr[0];

        int l = arr[0] + k;
        int r = arr[n - 1] - k;
        for (int i = 0; i < n - 1; i++) {
            int mini = Math.min(l, arr[i + 1] - k);
            int maxi = Math.max(r, arr[i] + k);

            if (mini >= 0)
                ans = Math.min(ans, maxi - mini);
        }

        return ans;
    }
}

Was this solution helpful?