10. Minimise the Maximum Difference Between Heights

You are given the heights of n towers and a value k. Each tower's height must be either increased or decreased by exactly k (once, your choice per tower). Minimize the difference between the tallest and shortest tower after these changes, and print that minimum difference.

Input: The first line contains two integers n and k. The second line contains n space-separated integers, the tower heights. Output: Print a single integer - the minimum possible difference between the tallest and shortest tower after adjusting each by k.

1 <= n <= 10^5, 0 <= k <= 10^9

Sorting first is what makes the 'contiguous split' insight even meaningful - without sorting, there's no clean notion of 'before' and 'after' a split point at all.

Every tower's height must be adjusted up or down by a fixed amount k (your choice which direction, per tower). Minimize the gap between the tallest and shortest tower after all the adjustments. Brute force: Try every possible COMBINATION of up/down choices per tower independently - this is exponential (2^n combinations), completely impractical beyond very small inputs. Optimised: Sorting first reveals that only 'contiguous splits' (everything before some point goes up, everything from that point onward goes down) ever need to be considered for an OPTIMAL solution - trying every one of the n possible split points, and computing the resulting spread in constant time per split using the sorted order's known extremes, reduces an exponential search down to a linear one after the initial sort.

For every tower, try both choices (height + k or height - k) via recursive backtracking over all n towers, and for each complete assignment compute the resulting maximum minus minimum height, keeping track of the smallest such difference seen across all 2^n assignments. This is correct because it literally checks every possible outcome, but the number of assignments doubles with each tower, making it impractical for anything beyond very small n. Time: O(2^n * n) Space: O(n)

Sort the towers, initialize the answer with the no-change case (last element minus first element), then walk through each split point once while incrementally maintaining the running high value as max(height of element just before the split + k, tallest element + k, or the last element - k) and the running low value as min(shortest element + k, next element after the split - k), updating the best answer at each step. This is correct because sorting guarantees the candidates for the new max and min after any split come only from a small fixed set of boundary elements, and tracking them incrementally as the split moves avoids ever rescanning the array, cutting the per-split cost down to constant time. Time: O(n log n) Space: O(1)

Sort the towers by height first, then consider only the n-1 meaningful ways to split the sorted array into a 'raise' group (elements before the split, each +k) and a 'lower' group (elements from the split onward, each -k), which is enough because sorting means the optimal assignment is always some prefix raised and some suffix lowered. For each split point, recompute the resulting maximum and minimum from scratch by scanning the relevant modified values, and keep the best (smallest) difference found. This narrows the search from exponential to a manageable set of candidate splits, though recomputing the max/min for each split independently still costs a full scan each time. Time: O(n^2) Space: O(1)

1. Sort the tower heights first. 2. Notice that in an optimal solution, there's always some split point: towers before the split go UP by k, towers from the split onward go DOWN by k. 3. For every possible split point, compute the resulting maximum and minimum height across the whole adjusted array. 4. Track the smallest such (max - min) spread found across all split points - that's your answer.

Time: O(n log n), dominated by the initial sort - checking every split point afterward is a linear O(n) pass. Space: O(1) extra space beyond the sort itself, since each split's resulting max/min can be computed directly from the sorted array's known boundary values.

Test n = 1 (difference is always 0), k = 0 (heights unchanged, difference is the original spread), and n = 10^5 for performance.

Be ready to justify WHY only contiguous splits need to be considered (rather than arbitrary independent per-tower choices) - this non-obvious reduction from exponential to linear is the entire crux of the problem, and interviewers often ask for this justification specifically.