662. The Tightest Spread After Removing Three

Remove exactly THREE values from the array, then take the largest of what remains minus the smallest. Make that spread as small as possible.

When four or fewer values are given, removing three leaves at most one, so the spread is 0.

5 3 2 4 -> 0 only one value is left 1 5 0 10 14 -> 1 removing 5, 10 and 14 leaves 0 and 1 1 2 3 4 5 6 -> 2

## Only the ends can be worth removing

The spread depends on the smallest and largest survivor and on nothing else. So there is never any point removing a value from the MIDDLE: doing so leaves the ends where they are and wastes a removal that could have trimmed one.

So after sorting, the three removals are taken entirely from the two ends.

## Four choices, not many

With three removals split between the front and the back there are exactly four ways:

3 from the front, 0 from the back 2 from the front, 1 from the back 1 from the front, 2 from the back 0 from the front, 3 from the back

For k removed from the front, the survivors run from index k to index n - 1 - (3 - k), so the spread is

a[n - 4 + k] - a[k]

Take the smallest over k from 0 to 3. That is the whole algorithm after the sort.

## Where the two pointers are

Each choice is a window with a cursor at each end, and the four choices slide those cursors inward by a total of three. Writing it as a loop over k is the same thing said shortly.

## Why the answer is not always achieved at a balanced split

It is tempting to remove one or two from each side by symmetry. The second sample is the counterexample. Sorted it is 0 1 5 10 14, and the four splits give:

remove 3 from the back -> 1 - 0 = 1 remove 2 from the back -> 5 - 1 = 4 remove 1 from the back -> 10 - 5 = 5 remove 0 from the back -> 14 - 10 = 4

The winner removes all three from ONE side, and both balanced splits are worse.

Checking all four is cheap and avoids having to reason about which side wins.

## Boundaries

Four or fewer values answer 0 and must be handled before indexing, or a[n - 4 + k] reads before the array.

All values equal answer 0.

## Cost

Time O(n log n) for the sort. Space O(1) beyond the input.

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ each value ≤ 10^9`