{x}
blog image

Smallest Range I

You are given an integer array nums and an integer k.

In one operation, you can choose any index i where 0 <= i < nums.length and change nums[i] to nums[i] + x where x is an integer from the range [-k, k]. You can apply this operation at most once for each index i.

The score of nums is the difference between the maximum and minimum elements in nums.

Return the minimum score of nums after applying the mentioned operation at most once for each index in it.

 

Example 1:

Input: nums = [1], k = 0
Output: 0
Explanation: The score is max(nums) - min(nums) = 1 - 1 = 0.

Example 2:

Input: nums = [0,10], k = 2
Output: 6
Explanation: Change nums to be [2, 8]. The score is max(nums) - min(nums) = 8 - 2 = 6.

Example 3:

Input: nums = [1,3,6], k = 3
Output: 0
Explanation: Change nums to be [4, 4, 4]. The score is max(nums) - min(nums) = 4 - 4 = 0.

 

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 104
  • 0 <= k <= 104

Solution Explanation for Smallest Range I

This problem asks to find the minimum difference between the maximum and minimum elements in an array after applying a transformation. The transformation allows adding or subtracting an integer x (where -k ≤ x ≤ k) to each element at most once.

The key insight is that the optimal strategy is to always try to bring the maximum and minimum elements closer together. We do this by adding k to the minimum element and subtracting k from the maximum element. This maximizes the reduction in the range.

Approach

  1. Find Maximum and Minimum: First, we find the maximum and minimum values in the input array nums. This can be done efficiently in O(n) time using a single pass through the array.

  2. Calculate Reduced Range: We then calculate the difference between the maximum and minimum values after applying the transformation: max(nums) - k - (min(nums) + k) = max(nums) - min(nums) - 2k.

  3. Handle Negative Range: The result from step 2 might be negative if the reduction exceeds the initial range. In such cases, the minimum possible range is 0 (when all elements become equal). Therefore, we return the maximum of 0 and the calculated reduced range.

Time and Space Complexity

  • Time Complexity: O(n), dominated by the initial pass to find the minimum and maximum values in the array.
  • Space Complexity: O(1), as we only use a few constant extra variables.

Code Implementation (Python)

class Solution:
    def smallestRangeI(self, nums: List[int], k: int) -> int:
        mx, mi = max(nums), min(nums)  #Find max and min in one pass
        return max(0, mx - mi - 2 * k)  #Calculate reduced range, handle negative case

Code Implementation (Java)

class Solution {
    public int smallestRangeI(int[] nums, int k) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) { //Find max and min in one pass
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        return Math.max(0, max - min - 2 * k); //Calculate reduced range, handle negative case
    }
}

Code Implementation (C++)

class Solution {
public:
    int smallestRangeI(vector<int>& nums, int k) {
        int max_val = *max_element(nums.begin(), nums.end()); //Find max and min using built-in functions. More concise
        int min_val = *min_element(nums.begin(), nums.end());
        return max(0, max_val - min_val - 2 * k);  //Calculate reduced range, handle negative case
    }
};

The other language implementations (Go, TypeScript, Rust) follow a very similar structure, employing the same core algorithmic idea for efficiency. They differ only in their syntax and standard library functions for finding maximum and minimum values.