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 <= 10000
0 <= A[i] <= 10000
0 <= 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;
}
}