##### Welcome to Subscribe On Youtube

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 = [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. 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[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;
}
}

• class Solution:
def smallestRangeII(self, nums: List[int], k: int) -> int:
nums.sort()
ans = nums[-1] - nums[0]
for i in range(1, len(nums)):
mi = min(nums[0] + k, nums[i] - k)
mx = max(nums[i - 1] + k, nums[-1] - k)
ans = min(ans, mx - mi)
return ans

############

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[0], A[-1]
res = mx - mn
for i in range(N - 1):
mx = max(A[i] + 2 * K, mx)
mn = min(A[i + 1], A[0] + 2 * K)
res = min(mx - mn, res)
return res

• class Solution {
public:
int smallestRangeII(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size();
int ans = nums[n - 1] - nums[0];
for (int i = 1; i < n; ++i) {
int mi = min(nums[0] + k, nums[i] - k);
int mx = max(nums[i - 1] + k, nums[n - 1] - k);
ans = min(ans, mx - mi);
}
return ans;
}
};

• func smallestRangeII(nums []int, k int) int {
sort.Ints(nums)
n := len(nums)
ans := nums[n-1] - nums[0]
for i := 1; i < n; i++ {
mi := min(nums[0]+k, nums[i]-k)
mx := max(nums[i-1]+k, nums[n-1]-k)
ans = min(ans, mx-mi)
}
return ans
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

func min(a, b int) int {
if a < b {
return a
}
return b
}