Problem Description

You have an integer array nums and an integer k. Your task is to modify each element in the array by either adding k to it or subtracting k from it. After modifying all elements, the score of the array is calculated as the difference between the maximum and minimum values in the modified array.

Your goal is to find the minimum possible score after applying the modifications to each element.

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

• Element at index 0: can become either 1 + 3 = 4 or 1 - 3 = -2
• Element at index 1: can become either 3 + 3 = 6 or 3 - 3 = 0
• Element at index 2: can become either 6 + 3 = 9 or 6 - 3 = 3

You need to choose whether to add or subtract k for each element such that the resulting array has the smallest possible difference between its maximum and minimum values.

The key insight is that to minimize the range, you want to bring the extreme values closer together. This means larger values should generally be decreased by k while smaller values should be increased by k. The solution sorts the array first, then considers different split points where elements before that point are increased by k and elements from that point onward are decreased by k.

Intuition

Let's think about what happens when we modify the array. Since we can either add or subtract k from each element, we're essentially given two choices for each number. The challenge is figuring out which operation to apply to minimize the final range.

Consider a sorted array. The original range is nums[-1] - nums[0]. Now, if we want to minimize the range after modifications, we should try to make the smallest values larger and the largest values smaller. This suggests:

• Smaller elements should have k added to them
• Larger elements should have k subtracted from them

But where exactly should we switch from adding to subtracting? This is the key question.

Imagine drawing a dividing line somewhere in the sorted array. Everything to the left of this line gets +k, and everything to the right gets -k. The new minimum value would be either:

• The smallest element plus k (from the left group)
• The smallest element from the right group minus k

Similarly, the new maximum would be either:

• The largest element from the left group plus k
• The largest element minus k (from the right group)

Since we don't know where the optimal dividing line is, we need to try all possible positions. For each position i, we consider:

• Elements [0, i-1] get +k
• Elements [i, n-1] get -k

For each split point, the minimum could be min(nums[0] + k, nums[i] - k) and the maximum could be max(nums[i-1] + k, nums[-1] - k). We calculate the range for each split and keep track of the minimum range found.

This greedy approach works because once the array is sorted, the optimal solution must follow this pattern of adding k to a prefix and subtracting k from a suffix.

Learn more about Greedy, Math and Sorting patterns.

Solution Approach

The implementation follows a greedy approach combined with enumeration of all possible split points:

1. Sort the array: First, we sort nums in ascending order. This allows us to systematically consider which elements should be increased and which should be decreased.

2. Initialize the answer: We start with the original range as our initial answer: ans = nums[-1] - nums[0]. This represents the case where all elements are modified in the same direction (all +k or all -k), which doesn't change the range.

3. Enumerate split points: We iterate through each possible split position i from 1 to len(nums) - 1. At each position i:

   • Elements from index 0 to i-1 will have k added
   • Elements from index i to the end will have k subtracted

4. Calculate new range for each split: For each split point i:

   • The new minimum value is mi = min(nums[0] + k, nums[i] - k)
     • Either the smallest element increased by k
     • Or the first element in the "subtract" group decreased by k
   • The new maximum value is mx = max(nums[i-1] + k, nums[-1] - k)
     • Either the last element in the "add" group increased by k
     • Or the largest element decreased by k
   • The range for this split is mx - mi

5. Track the minimum: We update ans = min(ans, mx - mi) to keep track of the minimum range found across all split points.

6. Return the result: After trying all possible splits, we return the minimum range found.

The time complexity is O(n log n) due to sorting, where n is the length of the array. The space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the algorithm with nums = [1, 3, 6] and k = 3.

Step 1: Sort the array Array is already sorted: [1, 3, 6]

Step 2: Initialize answer ans = nums[2] - nums[0] = 6 - 1 = 5

Step 3: Try each split point

Split at i=1: Elements before index 1 get +k, elements from index 1 onward get -k

• Elements: [1] get +3 → [4]
• Elements: [3, 6] get -3 → [0, 3]
• Modified array values: [4, 0, 3]
• New minimum: mi = min(nums[0] + k, nums[1] - k) = min(1 + 3, 3 - 3) = min(4, 0) = 0
• New maximum: mx = max(nums[0] + k, nums[2] - k) = max(1 + 3, 6 - 3) = max(4, 3) = 4
• Range: mx - mi = 4 - 0 = 4
• Update: ans = min(5, 4) = 4

Split at i=2: Elements before index 2 get +k, elements from index 2 onward get -k

• Elements: [1, 3] get +3 → [4, 6]
• Elements: [6] get -3 → [3]
• Modified array values: [4, 6, 3]
• New minimum: mi = min(nums[0] + k, nums[2] - k) = min(1 + 3, 6 - 3) = min(4, 3) = 3
• New maximum: mx = max(nums[1] + k, nums[2] - k) = max(3 + 3, 6 - 3) = max(6, 3) = 6
• Range: mx - mi = 6 - 3 = 3
• Update: ans = min(4, 3) = 3

Step 4: Return result The minimum possible score is 3.

This occurs when we add k to the first two elements [1, 3] → [4, 6] and subtract k from the last element [6] → [3], giving us the modified array [4, 6, 3] with range 6 - 3 = 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the sorting operation nums.sort(), which takes O(n × log n) time where n is the length of the input array. After sorting, there is a single loop that iterates through the array once with O(1) operations inside the loop, contributing O(n) time. Therefore, the overall time complexity is O(n × log n) + O(n) = O(n × log n).

Space Complexity: O(log n)

The space complexity comes from the sorting algorithm. Python's built-in sort() method uses Timsort, which requires O(log n) space in the worst case for its recursive call stack. The rest of the algorithm uses only a constant amount of extra space for variables like ans, mi, and mx. Therefore, the overall space complexity is O(log n).

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

Common Pitfalls

1. Forgetting to Handle the No-Split Cases

A common mistake is not considering the cases where all elements should be modified in the same direction (all +k or all -k). While the code initializes with nums[-1] - nums[0], developers sometimes forget this initialization and only focus on the split enumeration, leading to incorrect results.

Why it matters: For some inputs, the optimal solution is to move all elements in the same direction. For example, if the array is already tightly clustered, splitting might actually increase the range.

Solution: Always initialize the answer with the original range before iterating through split points:

min_range = nums[-1] - nums[0]  # Don't forget this initialization!

2. Incorrect Split Point Logic

Developers often confuse which elements should get +k and which should get -k. The intuition that "smaller values should increase and larger values should decrease" can lead to off-by-one errors in the split implementation.

Common mistake:

# Wrong: Using nums[i] + k instead of nums[i] - k
new_min = min(nums[0] + k, nums[i] + k)  # Incorrect!

Solution: Remember that at split point i:

• Elements [0, i-1] get +k (move up)
• Elements [i, n-1] get -k (move down)

So the correct calculation is:

new_min = min(nums[0] + k, nums[i] - k)  # First element of "subtract" group
new_max = max(nums[i-1] + k, nums[-1] - k)  # Last element of "add" group

3. Not Sorting the Array First

Some developers attempt to solve this problem without sorting, thinking they can apply the operations directly. This makes it impossible to determine the optimal split point efficiently.

Why sorting is essential: Without sorting, you cannot systematically decide which elements should be increased versus decreased. The sorted order allows you to consider contiguous groups for each operation.

Solution: Always sort first:

nums.sort()  # Critical first step!

4. Edge Case: Single Element Array

While the given code handles this correctly due to the loop range, developers writing their own solution might not handle arrays with only one element properly.

Solution: The loop range(1, len(nums)) naturally handles this by not executing when len(nums) == 1, returning the initialized value of 0 (since nums[-1] - nums[0] = 0 for a single element).

5. Integer Overflow Concerns (Language-Specific)

In languages with fixed integer sizes (like C++ or Java), calculating nums[i] + k or nums[i] - k might cause overflow for large values.

Solution for other languages: Use appropriate data types (e.g., long long in C++) or check for potential overflow conditions. Python handles arbitrary precision integers automatically, so this isn't a concern in the provided code.