Approach 1: Mathematical
Intuition and Algorithm
A be the original array, and
B be the array after all our modifications. Towards trying to minimize
max(B) - min(B), let's try to minimize
max(B) and maximize
The smallest possible value of
max(A) - K, as the value
max(A) cannot go lower. Similarly, the largest possible value of
min(A) + K. So the quantity
max(B) - min(B) is at least
ans = (max(A) - K) - (min(A) + K).
We can attain this value (if
ans >= 0), by the following modifications:
- If , then
- Else, if , then
- Else, .
ans < 0, the best answer we could have is
ans = 0, also using the same modification.
Time Complexity: , where is the length of
Space Complexity: .
Analysis written by: @awice.