Smallest Range II
Problem
Given an integer array nums and an integer k, for every element you must add either +k or −k to it (exactly once each). Return the smallest possible difference between the maximum and minimum values of the resulting array.
nums = [1, 3, 6], k = 33def smallest_range_ii(nums, k):
nums.sort()
n = len(nums)
ans = nums[-1] - nums[0]
for i in range(n - 1):
hi = max(nums[-1] - k, nums[i] + k)
lo = min(nums[0] + k, nums[i + 1] - k)
ans = min(ans, hi - lo)
return ansfunction smallestRangeII(nums, k) {
nums.sort((a, b) => a - b);
const n = nums.length;
let ans = nums[n - 1] - nums[0];
for (let i = 0; i < n - 1; i++) {
const hi = Math.max(nums[n - 1] - k, nums[i] + k);
const lo = Math.min(nums[0] + k, nums[i + 1] - k);
ans = Math.min(ans, hi - lo);
}
return ans;
}class Solution {
public int smallestRangeII(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int ans = nums[n - 1] - nums[0];
for (int i = 0; i < n - 1; i++) {
int hi = Math.max(nums[n - 1] - k, nums[i] + k);
int lo = Math.min(nums[0] + k, nums[i + 1] - k);
ans = Math.min(ans, hi - lo);
}
return ans;
}
}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 = 0; i < n - 1; i++) {
int hi = max(nums[n - 1] - k, nums[i] + k);
int lo = min(nums[0] + k, nums[i + 1] - k);
ans = min(ans, hi - lo);
}
return ans;
}Explanation
Every number must change by either +k or -k, and we want the smallest possible spread between the new maximum and minimum. The key realization is that after sorting the array, the best strategy is to add +k to a prefix of small numbers and subtract k from the suffix of large numbers.
Why a clean prefix/suffix split? Raising small values and lowering large values pulls everything toward the middle. Once sorted, the optimal split always happens at one of the boundaries between adjacent elements, so we just try every split point.
For a split after index i, the new maximum is either the largest element minus k or nums[i] + k, so hi = max(nums[n-1] - k, nums[i] + k). Likewise the new minimum is lo = min(nums[0] + k, nums[i+1] - k). The candidate range is hi - lo, and we keep the smallest over all splits, starting from the baseline nums[n-1] - nums[0].
Example: nums = [1, 3, 6], k = 3. Baseline range is 6 - 1 = 5. Splitting after index 1 gives +3 to [1,3] and -3 to [6] → values [4, 6, 3], range 6 - 3 = 3, which is the answer.
Trying every boundary and keeping the minimum guarantees we find the tightest achievable range.