Smallest Range
Given an array A
of integers, for each integer A[i]
we may choose any x
with -K <= x <= K
, and add x
to A[i]
.
After this process, we have some array B
.
Return the smallest possible difference between the maximum value of B
and the minimum value of B
.
Solution
If we want to find the smallest possible difference between max(B) and min(B), we will have to try to minimize max(B) - min(B). We should try to minimize max(B), then maximize min(B).
The smallest possible value of max(B) is max(A) - K since - K is the most we can subtract from max(A). Similarly, the largest possible value of min(B) is min(A) + K since K is the most we can add to min(A). So the smallest we can make max(B) - min(B) is (max(A) - K) - (min(A) + K) = max(A) - min(A) - 2K.