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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

Mathematics

Greedy algorithms

Starter code: class Solution:
    def smallestRangeII(self, A: List[int], K: int) -> int:
        

Solutions:
class Solution:

	def smallestRangeII(self, A: List[int], K: int) -> int:
		if not A:
			return 0
		nums = sorted([num + K for num in set(A)], reverse=True)
		max_num = nums[0]
		min_num = nums[-1]
		changed_max = max_num - 2 * K
		res = max_num - min_num
		for i in range(len(nums) - 1):
			changed = nums[i] - 2 * K
			max_num = max(nums[i + 1], changed, changed_max)
			min_num = min(min_num, changed)
			res = min(res, max_num - min_num)
		return res


class Solution:

	def smallestRangeII(self, A: List[int], K: int) -> int:
		A.sort()
		minA = A[0]
		maxA = A[-1]
		smallest = maxA - minA
		for i in range(len(A) - 1):
			a = A[i]
			b = A[i + 1]
			smallest = min(smallest, max(maxA - K, a + K) - min(minA + K, b - K))
		return smallest


class Solution:

	def smallestRangeII(self, A: List[int], K: int) -> int:
		A.sort()
		(mi, ma) = (A[0], A[-1])
		ans = ma - mi
		for i in range(len(A) - 1):
			(a, b) = (A[i], A[i + 1])
			ans = min(ans, max(ma - K, a + K) - min(mi + K, b - K))
		return ans


class Solution:

	def smallestRangeII(self, A: List[int], K: int) -> int:
		A.sort()
		diff = A[-1] - A[0]
		for i in range(len(A) - 1):
			lower = min(A[0] + 2 * K, A[i + 1])
			upper = max(A[-1], A[i] + 2 * K)
			diff = min(diff, abs(upper - lower))
		return diff


class Solution:

	def smallestRangeII(self, A: List[int], K: int) -> int:
		if K == 0:
			return max(A) - min(A)
		if len(A) == 1:
			return 0
		if max(A) - min(A) <= K:
			return max(A) - min(A)
		else:
			A = sorted(A)
			dp = [A[-1] - A[0]]
			(n1, n2) = (A[-1] - K, A[0] + K)
			for i in range(len(A) - 1):
				dp += [max(A[i] + K, A[-1] - K) - min(A[0] + K, A[i + 1] - K)]
			return min(dp)


class Solution:

	def smallestRangeII(self, A: List[int], K: int) -> int:
		if len(A) == 1:
			return 0
		A.sort()
		i = 0
		j = len(A) - 1
		min_diff = A[-1] - A[0]
		bottom = A[0]
		peak = A[-1]
		for idx in range(len(A) - 1):
			(current, _next) = (A[idx], A[idx + 1])
			bottom = min(A[0] + K, _next - K)
			peak = max(A[-1] - K, current + K)
			min_diff = min(min_diff, peak - bottom)
		return min_diff


class Solution:

	def smallestRangeII(self, A: List[int], K: int) -> int:
		A.sort()
		res = A[-1] - A[0]
		for i in range(len(A) - 1):
			res = min(res, max(A[i] + K, A[-1] - K) - min(A[0] + K, A[i + 1] - K))
		return res


class Solution:

	def smallestRangeII(self, A: List[int], K: int) -> int:
		if not A:
			return 0
		A.sort()
		x = A[0]
		y = A[-1]
		res = y - x
		for i in range(len(A)):
			A[i] += 2 * K
			x = min(A[0], A[(i + 1) % len(A)])
			y = max(A[i], y)
			res = min(res, y - x)
		return res


class Solution:

	def smallestRangeII(self, A: List[int], k: int) -> int:
		A.sort()
		n = len(A)
		res = A[n - 1] - A[0]
		for i in range(n - 1):
			mn = min(A[i + 1] - k, A[0] + k)
			mx = max(A[i] + k, A[n - 1] - k)
			res = min(res, mx - mn)
		return res


class Solution:

	def smallestRangeII(self, A: List[int], K: int) -> int:
		A.sort()
		min_diff = A[-1] - A[0]
		for i in range(len(A) - 1):
			v_min = min(A[0] + K, A[i + 1] - K)
			v_max = max(A[i] + K, A[-1] - K)
			min_diff = min(min_diff, v_max - v_min)
		return min_diff


class Solution:

	def smallestRangeII(self, arr: List[int], k: int) -> int:
		arr.sort()
		best = arr[-1] - arr[0]
		for i in range(1, len(arr)):
			current_max = max(arr[-1] - k, arr[i - 1] + k)
			current_min = min(arr[0] + k, arr[i] - k)
			best = min(best, current_max - current_min)
		return best


class Solution:

	def smallestRangeII(self, A: List[int], k: int) -> int:
		A.sort()
		(res, n) = (A[-1] - A[0], len(A))
		temp = [max(A[n - 1] - k, A[n - i - 2] + k) - min(A[0] + k, A[n - i - 1] - k) for i in range(n)]
		return min(res, min(temp))


class Solution:

	def smallestRangeII(self, A: List[int], K: int) -> int:
		N = len(A)
		if N == 1:
			return 0
		A.sort()
		diff = A[-1] - A[0]
		for i in range(N - 1):
			maxi = max(A[i] + K, A[N - 1] - K)
			mini = min(A[0] + K, A[i + 1] - K)
			diff = min(diff, maxi - mini)
		return diff