Minimise the maximum difference between heights
Problem
You are given tower heights and an integer k. You must change every tower exactly once, either adding k or subtracting k. Heights must not become negative. Return the smallest possible difference between the tallest and the shortest tower afterwards.
Example 1
Input: heights = [1, 5, 8, 10], k = 2 Output: 5
Becomes [3, 3, 6, 8]: 8 − 3 = 5.
Also asked as: Minimise the maximum difference between heights
Test cases
Case 1
Input: [1,5,8,10], 2 Expected: 5
Case 2
Input: [3,9,12,16,20], 3 Expected: 11
Case 3
Input: [1,15,10], 6 Expected: 5
Case 4
Input: [4], 3 Expected: 0
View solutionHide solution1 approach
1. Sort, then try every split point
Time O(n log n)Space O(1)
Sorted, add k to a prefix and subtract k from the suffix. For each split, the new range is max(a[i-1]+k, a[n-1]-k) − min(a[0]+k, a[i]-k).
function getMinDiff(a, k) { a.sort((x, y) => x - y); const n = a.length; let ans = a[n - 1] - a[0]; for (let i = 1; i < n; i++) { if (a[i] - k < 0) continue; const high = Math.max(a[i - 1] + k, a[n - 1] - k); const low = Math.min(a[0] + k, a[i] - k); ans = Math.min(ans, high - low); } return ans;}