Formatted question description: https://leetcode.ca/all/910.html
910. Smallest Range II
Level
Medium
Description
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 <= 100000 <= A[i] <= 100000 <= K <= 10000
Solution
First sort the array A, find the maximum element and the minimum element and calculate the difference.
Next consider whether each number should be added K or -K. For any two numbers num1 and num2, if num1 < num2, then adding K to num1 and adding -K to num2 is always optimal.
After A is sorted, find the maximum index i such that A[i] should be added K, and the minimum difference can be obtained.
class Solution {
public int smallestRangeII(int[] A, int K) {
Arrays.sort(A);
int length = A.length;
int min = A[0], max = A[length - 1];
int difference = max - min;
for (int i = 1; i < length; i++) {
int num1 = A[i - 1], num2 = A[i];
int high = Math.max(A[length - 1] - K, num1 + K);
int low = Math.min(A[0] + K, num2 - K);
difference = Math.min(difference, high - low);
}
return difference;
}
}