Problem Description

Given an array A of integers and an integer K, you can choose to either add K or subtract K to each element of the array exactly once. After performing these operations, you want to minimize the difference between the largest and smallest element in the resulting array.

Constraints:

• Each element in A must be modified by either adding or subtracting K, not both.
• You must apply the operation to every element.
• The goal is to minimize max(A) - min(A) after all modifications.

Example:
Input: A = [1,3,6], K = 3
Output: 3
Explanation: After changing the array to [4,6,3] or [4,0,9] etc., the smallest possible difference is 3.

Thought Process

At first glance, it might seem that every element should be increased or decreased by K in a way that brings all values as close together as possible. A brute-force approach would try all 2^n combinations of adding or subtracting K for each element, but this quickly becomes infeasible for large arrays.

To optimize, we notice that after sorting the array, the biggest gap is usually between the smallest and largest elements. If we could "move" the small numbers up and the large numbers down (or vice versa), we could potentially shrink the range. The key insight is to consider the effect of changing the "cut" or "partition" in the sorted array, where all elements to the left get increased by K and all to the right get decreased by K.

This leads to a more efficient approach that tries all possible partition points after sorting, instead of all combinations.

Solution Approach

• Step 1: Sort the Array
  Sorting A helps us handle the elements in order, making it easier to reason about the minimum and maximum values after modification.
• Step 2: Initialize the Result
  The initial result is simply A[-1] - A[0] (the difference between the largest and smallest elements in the original array).
• Step 3: Try All Partition Points
  • For each index i from 0 to len(A) - 2:
  • Imagine increasing all elements up to i by K, and decreasing all elements after i by K.
  • Calculate the new min and max for this partition:
    • high = max(A[i] + K, A[-1] - K)
    • low = min(A[0] + K, A[i+1] - K)
  • Update the result if high - low is smaller than the previous result.
• Step 4: Return the Minimum Range
  After considering all partition points, return the smallest range found.

This approach efficiently finds the optimal way to add or subtract K to each element, without checking all possible combinations.

Example Walkthrough

Input: A = [1, 3, 6], K = 3

1. Sort A: [1, 3, 6]
2. Initial result: 6 - 1 = 5
3. Try partition after index 0:
   • Increase A[0]: 1 + 3 = 4
   • Decrease A[1] and A[2]: 3 - 3 = 0, 6 - 3 = 3
   • But per algorithm, we calculate:
     • high = max(A[0]+K, A[2]-K) = max(4, 3) = 4
     • low = min(A[0]+K, A[1]-K) = min(4, 0) = 0
     • Range: 4 - 0 = 4
4. Try partition after index 1:
   • Increase A[0] and A[1]: 1 + 3 = 4, 3 + 3 = 6
   • Decrease A[2]: 6 - 3 = 3
   • Per algorithm:
     • high = max(A[1]+K, A[2]-K) = max(6, 3) = 6
     • low = min(A[0]+K, A[2]-K) = min(4, 3) = 3
     • Range: 6 - 3 = 3
5. Minimum range found is 3.

Thus, the answer is 3.

Time and Space Complexity

Brute-force approach:

• Would try all 2^n ways to add or subtract K for each element.
• Time Complexity: O(2^n)
• Space Complexity: O(n) for recursion stack or storing combinations.

• Sorting the array: O(n \log n)
• Iterating through n-1 partition points: O(n)
• Total Time Complexity: O(n \log n)
• Space Complexity: O(1) (if sorting in-place), otherwise O(n)

Summary

The key to solving Smallest Range II efficiently is recognizing that, after sorting, we can minimize the range by considering all possible ways to "partition" the array into two groups: those increased by K and those decreased by K. This reduces the problem from exponential to linear time after sorting. The algorithm is both elegant and practical, making use of sorting and a single pass to test all possible splits, and ensures the smallest possible range is found.

Code Implementation

class Solution:
    def smallestRangeII(self, A, K):
        A.sort()
        res = A[-1] - A[0]
        for i in range(len(A) - 1):
            high = max(A[i] + K, A[-1] - K)
            low = min(A[0] + K, A[i+1] - K)
            res = min(res, high - low)
        return res
      

class Solution {
public:
    int smallestRangeII(vector<int>& A, int K) {
        sort(A.begin(), A.end());
        int n = A.size();
        int res = A[n-1] - A[0];
        for (int i = 0; i < n - 1; ++i) {
            int high = max(A[i] + K, A[n-1] - K);
            int low = min(A[0] + K, A[i+1] - K);
            res = min(res, high - low);
        }
        return res;
    }
};
      

class Solution {
    public int smallestRangeII(int[] A, int K) {
        Arrays.sort(A);
        int n = A.length;
        int res = A[n-1] - A[0];
        for (int i = 0; i < n - 1; ++i) {
            int high = Math.max(A[i] + K, A[n-1] - K);
            int low = Math.min(A[0] + K, A[i+1] - K);
            res = Math.min(res, high - low);
        }
        return res;
    }
}
      

var smallestRangeII = function(A, K) {
    A.sort((a, b) => a - b);
    let res = A[A.length - 1] - A[0];
    for (let i = 0; i < A.length - 1; ++i) {
        let high = Math.max(A[i] + K, A[A.length - 1] - K);
        let low = Math.min(A[0] + K, A[i + 1] - K);
        res = Math.min(res, high - low);
    }
    return res;
};