Problem Description

You have an integer array nums and an integer k.

For each element in the array, you can perform at most one operation. The operation allows you to pick any index i (where 0 <= i < nums.length) and modify nums[i] by adding any integer x from the range [-k, k]. This means you can add any value between -k and k (inclusive) to each element, but only once per element.

The score of the array is defined as the difference between the maximum element and the minimum element in nums.

Your task is to find the minimum possible score after applying the operation at most once to each element in the array.

For example, if you have nums = [1, 3, 6] and k = 3:

• You could add 3 to the first element (making it 4)
• You could subtract 3 from the last element (making it 3)
• After these operations, the array becomes [4, 3, 3]
• The score would be 4 - 3 = 1

The key insight is that to minimize the score, you want to bring the maximum and minimum values as close together as possible. You can decrease the maximum value by subtracting k from it, and increase the minimum value by adding k to it. The resulting minimum score would be max(0, original_max - original_min - 2*k), where we take the maximum with 0 because the score cannot be negative (if the adjustments cause the values to overlap or cross).

Intuition

To minimize the difference between the maximum and minimum values in the array, we need to think about how to bring these two extreme values as close together as possible.

Since we can add any value from [-k, k] to each element, the best strategy is to:

• Decrease the maximum value as much as possible (by subtracting k)
• Increase the minimum value as much as possible (by adding k)

Let's visualize this with a number line. If the original minimum is at position min and the original maximum is at position max, after the operations:

• The minimum can move up to min + k
• The maximum can move down to max - k

The new difference becomes (max - k) - (min + k) = max - min - 2k.

However, there's an important edge case to consider: what if 2k is larger than the original difference max - min? In this case, the minimum and maximum values can actually "cross over" or meet at the same point. When this happens, we can make all elements equal (or very close), resulting in a score of 0.

For example, if nums = [1, 3] and k = 2:

• Original difference: 3 - 1 = 2
• We can add 1 to the first element to get 2
• We can subtract 1 from the second element to get 2
• Both elements become 2, so the score is 0

Therefore, the formula max(0, max(nums) - min(nums) - 2*k) captures both scenarios:

• When max - min > 2k, the minimum score is max - min - 2k
• When max - min <= 2k, the minimum score is 0 (we can make all elements converge to the same value or very close values)

Learn more about Math patterns.

Solution Approach

The solution implements a straightforward mathematical approach based on our intuition:

1. Find the extremes: First, we identify the maximum and minimum values in the array using Python's built-in max() and min() functions:

   mx, mi = max(nums), min(nums)

2. Calculate the minimum score: We apply the formula we derived:

   • The original difference is mx - mi
   • We can reduce this difference by 2 * k (by adding k to the minimum and subtracting k from the maximum)
   • The result is mx - mi - 2 * k

3. Handle the edge case: If mx - mi - 2 * k is negative, it means we can make all elements converge to the same value or overlapping ranges, resulting in a score of 0. We handle this using:

   return max(0, mx - mi - k * 2)

The entire solution is elegant in its simplicity - no loops, no complex data structures, just a direct mathematical calculation. The time complexity is O(n) for finding the max and min values, and the space complexity is O(1) as we only use a constant amount of extra space.

This approach works because we don't need to actually modify the array or track individual elements. We only care about the extreme values and how much we can bring them closer together. The maximum reduction possible is 2 * k, and if this reduction exceeds the original difference, we can achieve a score of 0.

Example Walkthrough

Let's walk through a concrete example with nums = [1, 3, 6, 9] and k = 2.

Step 1: Identify the extremes

• Maximum value: 9
• Minimum value: 1
• Original difference: 9 - 1 = 8

Step 2: Apply the optimal strategy

• We can add up to k = 2 to the minimum: 1 + 2 = 3
• We can subtract up to k = 2 from the maximum: 9 - 2 = 7
• New difference: 7 - 3 = 4

Step 3: Verify with the formula

• Using max(0, mx - mi - 2*k):
• max(0, 9 - 1 - 2*2) = max(0, 8 - 4) = max(0, 4) = 4

The minimum possible score is 4.

Let's trace through what happens to each element:

• nums[0] = 1: Add 2 → becomes 3
• nums[1] = 3: Add any value in [-2, 2] → can stay as 3 or become anything from 1 to 5
• nums[2] = 6: Add any value in [-2, 2] → can become anything from 4 to 8
• nums[3] = 9: Subtract 2 → becomes 7

After operations, one possible array is [3, 3, 6, 7] with score 7 - 3 = 4.

Edge Case Example: nums = [4, 6] and k = 3

• Original difference: 6 - 4 = 2
• Using the formula: max(0, 6 - 4 - 2*3) = max(0, 2 - 6) = max(0, -4) = 0
• This makes sense because we can add 1 to 4 to get 5, and subtract 1 from 6 to get 5, making both elements equal with a score of 0.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because the max() and min() functions each iterate through the entire array once to find the maximum and minimum values respectively. Although these are two separate operations, they are sequential and not nested, resulting in O(n) + O(n) = O(n) overall time complexity.

The space complexity is O(1). The algorithm only uses a constant amount of extra space to store the variables mx and mi, regardless of the input size. No additional data structures that grow with the input size are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Operation Constraints

A common mistake is thinking that you must apply an operation to every element, or that you can apply multiple operations to the same element. The problem states "at most once" per element, meaning:

• You can choose not to modify an element at all (add 0 to it)
• You can only modify each element once
• You can add any value in the range [-k, k], not just ±k

Incorrect approach:

# Wrong: Assuming we must add exactly k or -k to every element
def smallestRangeI(self, nums: List[int], k: int) -> int:
    # This assumes we must maximize changes, which is incorrect
    return max(nums) - k - (min(nums) + k)

Correct understanding: The solution correctly handles this by recognizing we want to maximize the reduction in range, which means adding k to minimum values and subtracting k from maximum values.

2. Forgetting to Handle the Zero Case

When the range can be reduced to zero or negative (meaning all elements can be brought to the same value or overlapping ranges), forgetting to cap the result at 0 is a critical error.

Incorrect approach:

def smallestRangeI(self, nums: List[int], k: int) -> int:
    return max(nums) - min(nums) - 2 * k
    # This could return negative values, which doesn't make sense for a range

Correct approach:

def smallestRangeI(self, nums: List[int], k: int) -> int:
    return max(0, max(nums) - min(nums) - 2 * k)
    # Properly handles cases where elements can converge

3. Overcomplicating with Individual Element Tracking

Some might try to track what value to add to each element individually, sorting the array, or using complex data structures. This overcomplicates the problem since we only care about the extremes.

Overcomplicated approach:

def smallestRangeI(self, nums: List[int], k: int) -> int:
    nums.sort()  # Unnecessary sorting
    modified = []
    for i, num in enumerate(nums):
        if i < len(nums) // 2:
            modified.append(num + k)  # Add k to smaller half
        else:
            modified.append(num - k)  # Subtract k from larger half
    return max(modified) - min(modified)
    # This is unnecessarily complex and may not even give the optimal answer

The elegant solution recognizes that only the maximum and minimum values matter, and the optimal strategy is always to bring them as close together as possible by subtracting k from the max and adding k to the min.