Minimise the maximum difference between heights

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}