Approach 1: Linear Scan
As in Smallest Range I, smaller
A[i] will choose to increase their value ("go up"), and bigger
A[i] will decrease their value ("go down").
We can formalize the above concept: if
A[i] < A[j], we don't need to consider when
A[i] goes down while
A[j] goes up. This is because the interval
(A[i] + K, A[j] - K) is a subset of
(A[i] - K, A[j] + K) (here,
(a, b) for
a > b denotes
(b, a) instead.)
That means that it is never worse to choose
(up, down) instead of
(down, up). We can prove this claim that one interval is a subset of another, by showing both
A[i] + K and
A[j] - K are between
A[i] - K and
A[j] + K.
A[i] is the largest
i that goes up. Then
A + K, A[i] + K, A[i+1] - K, A[A.length - 1] - K are the only relevant values for calculating the answer: every other value is between one of these extremal values.
Time Complexity: , where is the length of the
Space Complexity: , plus the space used by the builtin sorting algorithm.
Analysis written by: @awice.