Formatted question description: https://leetcode.ca/all/910.html

# 910. Smallest Range II

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 = , K = 0

Output: 0

Explanation: B = 

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. 1 <= A.length <= 10000
2. 0 <= A[i] <= 10000
3. 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, 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 + K, num2 - K);
difference = Math.min(difference, high - low);
}
return difference;
}
}

• Todo

• class Solution(object):
def smallestRangeII(self, A, K):
"""
:type A: List[int]
:type K: int
:rtype: int
"""
A.sort()
N = len(A)
mn, mx = A, A[-1]
res = mx - mn
for i in range(N - 1):
mx = max(A[i] + 2 * K, mx)
mn = min(A[i + 1], A + 2 * K)
res = min(mx - mn, res)
return res