Smallest Range II

Problem Statement

In this problem, you are provided with an array of integers nums and a single integer k. You need to adjust each element in the array by either adding k to it or subtracting k from it. The aim is to minimize the difference between the maximum and minimum elements in the modified array. This difference is referred to as the score of the array nums. Your task is to determine the smallest possible score after making the adjustments to each element in the array.

Examples

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:

3

Explanation:

Change nums to be [4, 6, 3]. The score is max(nums) - min(nums) = 6 - 3 = 3.

Constraints

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

Approach and Intuition

To solve this problem, consider the following steps and intuitions derived from the examples:

1. Observe that for a given element in nums, the possible new values are only two: nums[i] + k and nums[i] - k.

2. The goal is to minimize the range (difference between maximum and minimum) of the new values across the entire array.

3. One straightforward way to approach this is:

   • Initially, sort the array to handle elements in a definite order.
   • Consider the smallest and largest possible numbers in the transformed array by looking at the first and last elements of the sorted array.
   • For every number nums[i], calculate its possible new values (nums[i] + k and nums[i] - k).
   • Calculate the potential new maximum and minimum for the array after each transformation.

4. The critical part of the solution involves deciding whether to increase or decrease each number by k dependent on its relative position in the current sorted order:

   • Increment the smaller half of the array by k (to potentially decrease the minimum of the range).
   • Decrement the larger half of the array by k (to potentially decrease the maximum of the range).

5. Between these operations, always take the difference between the current maximum and minimum, update if this is the smallest seen so far.

These steps ensure that by strategically manipulating values around the median of the sorted array, we compress the range of nums. Thus, the score gets minimized effectively due to the balanced nature of the transformations.

Solutions

class Solution {
    public int minRangeDifference(int[] nums, int K) {
        int length = nums.length;
        Arrays.sort(nums);
        int minDiff = nums[length-1] - nums[0];

        for (int i = 0; i < nums.length - 1; ++i) {
            int lower = nums[i], upper = nums[i+1];
            int maxVal = Math.max(nums[length-1] - K, lower + K);
            int minVal = Math.min(nums[0] + K, upper - K);
            minDiff = Math.min(minDiff, maxVal - minVal);
        }
        return minDiff;
    }
}