Smallest Range Ii - Leetcode Solution

Problem Statement:

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]

Approach:

In this problem, we have to add either K or -K to all the elements of the array. So, we need to make a decision of adding K or -K in such a way that the difference between the maximum and minimum values is minimized. To solve this, we can sort the array first and then make a decision of adding K or -K to all the elements located on the left or right side of the middle element.

Let's say, we have sorted the array. If we add K to the elements on the left side of the middle element and -K to the elements on the right side, then we can get the smallest difference between the maximum and minimum elements.

To simplify this approach, we can try to add 2K to all the elements on the left side of the middle element and -2K to all the elements on the right side. This way, we can handle both the cases at once.

Let's say, after sorting the array, we have an element A[i] that is located to the left of the middle element. If we add 2K to this element, then we can get A[i]+2K. But, if we add -2K to the element located to the right of the middle element, then we can get A[i]+(-2K). So, in both the cases, we can get A[i]+2K - A[i]+(-2K) = 4K. Hence, by adding 2K to the elements on the left side and -2*K to the elements on the right side, we can get the minimum possible difference between the maximum and minimum elements.

Finally, after making the required modification to the array, we can find the difference between the maximum and minimum elements, which will be the smallest possible range.

Solution:

Here is the implementation of the above approach in Python:

class Solution: def smallestRangeII(self, A: List[int], K: int) -> int: n = len(A) if n == 1: return 0 A.sort() ans = A[-1] - A[0] for i in range(n-1): high = max(A[i]+2K, A[-1]-2K) low = min(A[i+1]-2K, A[0]+2K) ans = min(ans, high-low) return ans

In this code, we sorted the input array A and initialized the answer (ans) by calculating the difference between the maximum and minimum elements of A. Then, we looped through the array and made the required modification to the elements of A. Finally, we calculated the difference between the maximum and minimum elements of the modified array and returned the smallest possible range.

The time complexity of this solution is O(nlogn), where n is the length of the input array. The space complexity is O(1).

1