Smallest Range II

LeetCode Q 910 - Smallest Range II

Given an array A of integers, for each integer A[i] we need to choose either x = -K or x = K, and add x to A[i] (only once).
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.

Example 1: Input: A = [1], K = 0 ; Output: 0
Explanation: B = [1]
Example 2: Input: A = [0,10], K = 2 ; Output: 6
Explanation: B = [2,8]
Example 3: Input: A = [1,3,6], K = 3 ; Output: 3
Explanation: B = [4,6,3]

Note:

• 1 <= A.length <= 10000
• 0 <= A[i] <= 10000
• 0 <= K <= 10000

Solution:

Comparing with Q908, for each integer in the array we can only + K or - K. So in this case after modification the maxinum and minimum number in array max(A) and min(A) may change.
But for ith and (i + 1)th number, we cannot do A[i] + K and A[i] - K to find the potential smallest diff between max and min.

Code:

public int smallestRangeII(int[] A, int K) {
  Arrays.sort(A);
  
  int min = A[0], max = A[A.length - 1];
  int res = max - min;
  
  for (int i = 0; i < A.length - 1; i++) {
    max = Math.max(A[i] + K, A[A.length - 1] - K);
    min = Math.min(A[i + 1] - K, A[0] + K);
    res = Math.min(max - min, res);
  }
  
  return res;
}