Code Implementation

class Solution:
    def smallestRangeI(self, nums, k):
        return max(0, max(nums) - min(nums) - 2 * k)
      

class Solution {
public:
    int smallestRangeI(vector<int>& nums, int k) {
        int mn = *min_element(nums.begin(), nums.end());
        int mx = *max_element(nums.begin(), nums.end());
        return max(0, mx - mn - 2 * k);
    }
};
      

class Solution {
    public int smallestRangeI(int[] nums, int k) {
        int mn = Integer.MAX_VALUE, mx = Integer.MIN_VALUE;
        for (int num : nums) {
            mn = Math.min(mn, num);
            mx = Math.max(mx, num);
        }
        return Math.max(0, mx - mn - 2 * k);
    }
}
      

var smallestRangeI = function(nums, k) {
    let mn = Math.min(...nums);
    let mx = Math.max(...nums);
    return Math.max(0, mx - mn - 2 * k);
};
      

Problem Description

You are given an array of integers nums and an integer k. For every element in nums, you are allowed to increase or decrease it by at most k (each element can be changed independently and by any value between -k and k, inclusive). After performing these operations, your goal is to find the smallest possible difference between the maximum and minimum elements in the array.

• Each element can be adjusted once, by up to k in either direction.
• Return the minimum possible difference between the largest and smallest numbers after all such adjustments.
• There is always at least one valid solution.

Thought Process

At first glance, it might seem that we need to try all possible combinations of increasing or decreasing each element by up to k and then find the minimum range. However, this quickly becomes infeasible for large arrays due to the huge number of possibilities.

Instead, let's think about the problem more strategically. If we want to minimize the difference between the maximum and minimum elements, we should try to bring the largest element down and the smallest element up as much as possible. Since every element can be shifted by at most k, the maximum element can be decreased by k and the minimum can be increased by k.

The key insight is that the minimum possible range after all operations is the original range minus 2 * k (since both ends can move by k), but it cannot be less than zero (if the numbers can overlap or cross).

Solution Approach

• Find the minimum value (min) and maximum value (max) in the array.
• The original range is max - min.
• After adjusting, the minimum value can be increased by k and the maximum value can be decreased by k.
• This means the new minimum is at least min + k and the new maximum is at most max - k.
• The new range is therefore (max - k) - (min + k) = (max - min) - 2 * k.
• If this value is negative, it means the numbers can overlap, so the smallest possible range is 0.
• Return max(0, (max - min) - 2 * k).

This approach is efficient, requiring only a single pass to find the min and max, and then a simple calculation.

Example Walkthrough

Let's take nums = [1, 3, 6] and k = 3.

• The minimum is 1, the maximum is 6.
• Original range: 6 - 1 = 5.
• If we increase 1 by 3, it becomes 4.
• If we decrease 6 by 3, it becomes 3.
• The new range can be as small as max(0, 6 - 1 - 2*3) = max(0, 5 - 6) = max(0, -1) = 0.
• This means, after adjustments, all numbers can overlap or become the same, so the smallest possible range is 0.

Another example: nums = [0, 10], k = 2.

• min = 0, max = 10, original range = 10.
• After operations, new range = max(0, 10 - 0 - 4) = max(0, 6) = 6.
• So the smallest possible range is 6.

Time and Space Complexity

• Brute-force approach: Would try all combinations of increasing/decreasing each element, leading to exponential time complexity O(2^n) (where n is the length of nums), which is infeasible.
• Optimized approach: We only need to find the min and max in one pass (O(n) time), and use O(1) extra space.
• Thus, the final solution is O(n) time and O(1) space.

Summary

To solve the "Smallest Range I" problem, we avoid brute-force by realizing that maximizing the increase of the smallest number and the decrease of the largest number gives the best result. The minimal possible range is the original range minus 2 * k, but it cannot go below zero. This approach is both efficient and elegant, requiring only min/max calculations and a simple formula.