Solution


Approach 1: Mathematical

Intuition and Algorithm

Let 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 min(B) separately.

The smallest possible value of max(B) is max(A) - K, as the value max(A) cannot go lower. Similarly, the largest possible value of min(B) is 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, .

If ans < 0, the best answer we could have is ans = 0, also using the same modification.

Complexity Analysis

  • Time Complexity: , where is the length of A.

  • Space Complexity: .


Analysis written by: @awice.