Smallest Range I

easy math greedy array

Problem

You are given an integer array nums and an integer k. In one operation you may add any integer in the range [-k, k] to one element of nums, applying the operation to each element at most once. Return the minimum possible difference between the largest and smallest values of nums after the changes.

Inputnums = [1, 3, 6], k = 2

Output1

Spread is max − min = 6 − 1 = 5. Raise the min by +2 and drop the max by −2, closing 2·2 = 4, so answer = max(0, 5 − 4) = 1.

Inputnums = [1, 3, 6], k = 3

Output0

Each end can move by k=3, closing up to 2·3 = 6 ≥ 5, so answer = max(0, 5 − 6) = 0.

nums (comma-separated)

def smallest_range_i(nums, k):
    lo = min(nums)
    hi = max(nums)
    spread = hi - lo
    return max(0, spread - 2 * k)

function smallestRangeI(nums, k) {
  const lo = Math.min(...nums);
  const hi = Math.max(...nums);
  const spread = hi - lo;
  return Math.max(0, spread - 2 * k);
}

class Solution {
    public int smallestRangeI(int[] nums, int k) {
        int lo = nums[0], hi = nums[0];
        for (int x : nums) { lo = Math.min(lo, x); hi = Math.max(hi, x); }
        int spread = hi - lo;
        return Math.max(0, spread - 2 * k);
    }
}

int smallestRangeI(vector<int>& nums, int k) {
    int lo = *min_element(nums.begin(), nums.end());
    int hi = *max_element(nums.begin(), nums.end());
    int spread = hi - lo;
    return max(0, spread - 2 * k);
}

Explanation

This looks like it needs trying many adjustments, but it's really a one-line formula. Only the smallest and largest values matter — everything in between can be tucked between them.

The current gap is spread = max - min. Each value can shift by up to k in either direction. To shrink the gap the most, we raise the min by +k and drop the max by -k, which closes the gap by 2k.

So the best achievable difference is spread - 2k, but it can't go below 0 (once the two ends meet or cross, they can all sit on one value). That's why the answer is max(0, spread - 2 * k).

Example: nums = [1, 3, 6], k = 2. spread = 6 - 1 = 5. We close 2·2 = 4, giving max(0, 5 - 4) = 1. With k = 3 we'd close 6 ≥ 5, so the answer is 0.

The middle elements never constrain anything because they can always be nudged to land inside the new, tighter range.

Time: O(n) Space: O(1)