Smallest Range II

Problem Description

You are given an integer array nums and an integer k. For each index i where 0 <= i < nums.length, change nums[i] to be either nums[i] + k or nums[i] - k. The score of nums is the difference between the maximum and minimum elements in nums. Return the minimum score of nums after changing the values at each index.

Key Insights

• The score is defined as the difference between the maximum and minimum values in the array.
• By adding or subtracting k to/from elements, the potential new maximum and minimum values can be determined.
• The optimal new maximum value can be the original maximum value minus k, and the optimal new minimum can be the original minimum value plus k.
• Sorting the array helps in easily identifying the new bounds for the maximum and minimum values after adjustments.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array.
Space Complexity: O(1) - we are using a constant amount of extra space.

Solution

To solve this problem, we can follow these steps:

1. Sort the input array to easily determine the minimum and maximum values.
2. Identify the potential new maximum and minimum values after adjusting each element by ±k.
3. Calculate the minimum score using the formula: max(nums) - min(nums) after adjustments.
4. Return the calculated minimum score.

The solution primarily uses sorting as the main data structure and employs a greedy approach to minimize the score.

Code Solutions