Problem Description

You have an integer array nums. You can perform a move by selecting any element in the array and changing it to any value you want.

Your goal is to minimize the difference between the maximum and minimum values in the array after performing at most 3 moves.

For example, if you have an array like [5, 3, 2, 4], after making up to 3 moves, you could change some elements to make the array have a smaller range between its largest and smallest values.

The problem asks you to return the minimum possible difference between the largest and smallest values after these modifications.

Key constraints:

• You can make 0, 1, 2, or 3 moves (but no more than 3)
• Each move allows you to change one element to any value
• You want to minimize max(nums) - min(nums) after the moves

Special case: If the array has 4 or fewer elements, you can change up to 3 of them, which means you can make all elements equal (resulting in a difference of 0).

The solution works by sorting the array and considering different combinations of removing elements from the beginning and end. Since we can change up to 3 elements, we effectively consider scenarios where we "remove" 0-3 elements from the left and 3-0 elements from the right, finding the minimum difference among all these combinations.

Intuition

Think about what happens when we can change up to 3 elements in the array. The key insight is that to minimize the difference between max and min, we should target the extreme values - either the largest elements or the smallest elements, or a combination of both.

Why? Because changing middle values doesn't help us reduce the range. If we have a sorted array like [1, 2, 3, 4, 100], changing the 3 to any value won't reduce the difference between 100 and 1. We need to deal with the extremes.

Since we can make up to 3 changes, we can effectively "remove" up to 3 problematic extreme values by changing them to values within our desired range. After sorting the array, these extreme values are at the ends.

Here's the critical realization: if we have n elements and can change 3 of them, we're essentially choosing which n-3 consecutive elements to keep from the sorted array. The difference will be determined by the range of these kept elements.

We have exactly 4 ways to distribute our 3 changes:

• Change 0 from left, 3 from right: keep elements from nums[0] to nums[n-4]
• Change 1 from left, 2 from right: keep elements from nums[1] to nums[n-3]
• Change 2 from left, 1 from right: keep elements from nums[2] to nums[n-2]
• Change 3 from left, 0 from right: keep elements from nums[3] to nums[n-1]

For each scenario, the minimum difference is the range of the kept elements. We try all 4 combinations and take the minimum.

When the array has 4 or fewer elements, we can change enough elements (3 out of 4 maximum) to make them all equal, giving us a difference of 0.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a straightforward approach based on our intuition:

Step 1: Handle Edge Case

if n < 5:
    return 0

When we have 4 or fewer elements, we can change up to 3 of them to make all elements equal, resulting in a difference of 0.

Step 2: Sort the Array

nums.sort()

Sorting allows us to easily identify and work with the extreme values at both ends of the array.

Step 3: Try All Possible Distributions

ans = inf
for l in range(4):
    r = 3 - l
    ans = min(ans, nums[n - 1 - r] - nums[l])

We iterate through all 4 possible ways to distribute our 3 changes:

• When l = 0: Remove 0 from left, 3 from right → difference is nums[n-4] - nums[0]
• When l = 1: Remove 1 from left, 2 from right → difference is nums[n-3] - nums[1]
• When l = 2: Remove 2 from left, 1 from right → difference is nums[n-2] - nums[2]
• When l = 3: Remove 3 from left, 0 from right → difference is nums[n-1] - nums[3]

The formula nums[n - 1 - r] - nums[l] calculates the range of elements we're keeping. Since r = 3 - l, when we skip l elements from the left and r elements from the right, our new maximum is at index n - 1 - r and our new minimum is at index l.

Step 4: Return the Minimum We track the minimum difference across all combinations and return it.

Time Complexity: O(n log n) due to sorting Space Complexity: O(1) if we don't count the sorting space, otherwise O(log n) for the sorting algorithm's stack space

Example Walkthrough

Let's walk through the solution with the array nums = [1, 5, 0, 10, 14].

Step 1: Check edge case

• Array has 5 elements (n = 5), which is ≥ 5, so we continue.

Step 2: Sort the array

• After sorting: nums = [0, 1, 5, 10, 14]

Step 3: Try all 4 distributions of our 3 moves

We can change up to 3 elements. Let's examine each way to distribute these changes:

Option 1 (l=0, r=3): Change 0 from left, 3 from right

• Keep elements from index 0 to index 1 (n-1-r = 5-1-3 = 1)
• Keep: [0, 1]
• Difference: nums[1] - nums[0] = 1 - 0 = 1

Option 2 (l=1, r=2): Change 1 from left, 2 from right

• Keep elements from index 1 to index 2 (n-1-r = 5-1-2 = 2)
• Keep: [1, 5]
• Difference: nums[2] - nums[1] = 5 - 1 = 4

Option 3 (l=2, r=1): Change 2 from left, 1 from right

• Keep elements from index 2 to index 3 (n-1-r = 5-1-1 = 3)
• Keep: [5, 10]
• Difference: nums[3] - nums[2] = 10 - 5 = 5

Option 4 (l=3, r=0): Change 3 from left, 0 from right

• Keep elements from index 3 to index 4 (n-1-r = 5-1-0 = 4)
• Keep: [10, 14]
• Difference: nums[4] - nums[3] = 14 - 10 = 4

Step 4: Return minimum

• Minimum of [1, 4, 5, 4] = 1

The answer is 1. This makes sense because if we change the three largest values (5, 10, 14) to values between 0 and 1, our array could become something like [0, 1, 1, 1, 1], giving us a range of 1 - 0 = 1.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n) where n is the length of the input array nums.

The dominant operation in this algorithm is the sorting step nums.sort(), which takes O(n log n) time. After sorting, the code performs a constant number of operations - specifically, it iterates exactly 4 times in the for loop (from l = 0 to l = 3), and in each iteration, it performs constant-time operations (array access and min comparison). Therefore, the post-sorting operations take O(1) time. The overall time complexity is O(n log n) + O(1) = O(n log n).

Space Complexity: O(1) or O(n) depending on the sorting algorithm implementation.

If the built-in sort() method uses an in-place sorting algorithm like heapsort, the space complexity would be O(1) as we only use a constant amount of extra space for variables n, ans, l, and r. However, Python's Timsort (the algorithm used by the built-in sort()) has a worst-case space complexity of O(n) for the temporary arrays it uses during the sorting process. Since we're sorting the input array in-place and not creating any additional data structures proportional to the input size (apart from what the sorting algorithm uses internally), the space complexity is determined by the sorting algorithm's requirements.

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

Common Pitfalls

1. Forgetting to Handle Small Arrays

One of the most common mistakes is not properly handling arrays with 4 or fewer elements. Without this check, the code will still work but miss the optimization opportunity.

Pitfall Example:

def minDifference(self, nums: List[int]) -> int:
    nums.sort()
    n = len(nums)
    min_diff = inf
  
    # This will cause index errors for arrays with less than 4 elements!
    for l in range(4):
        r = 3 - l
        min_diff = min(min_diff, nums[n - 1 - r] - nums[l])
  
    return min_diff

Why it fails: For an array like [1, 2], when l = 3, we try to access nums[3] which doesn't exist.

Solution: Always check array length first:

if len(nums) < 5:
    return 0

2. Misunderstanding the Problem - Thinking We Need to Actually Change Values

Some might overthink and try to determine what values to change elements to, rather than realizing we just need to "ignore" the extreme values.

Pitfall Example:

def minDifference(self, nums: List[int]) -> int:
    # Wrong approach: trying to find optimal values to change to
    nums.sort()
    median = nums[len(nums) // 2]
  
    # Changing closest 3 elements to median - INCORRECT!
    # This doesn't guarantee minimum difference

Solution: Understand that changing an element optimally means either:

• Making it equal to the minimum (if it was large)
• Making it equal to the maximum (if it was small)
• Making it something in between (which is equivalent to ignoring it)

Therefore, we only need to consider which elements to "remove" from consideration.

3. Off-by-One Errors in Index Calculation

When calculating the new maximum index after removing elements from the right, it's easy to make indexing mistakes.

Pitfall Example:

for l in range(4):
    r = 3 - l
    # Wrong: should be n - 1 - r, not n - r
    min_diff = min(min_diff, nums[n - r] - nums[l])

Why it fails: nums[n - r] when r = 0 would access nums[n], which is out of bounds.

Solution: Remember that the last element is at index n - 1, so after removing r elements from the right, the new maximum is at n - 1 - r.

4. Not Considering All Combinations

Some might think we should always remove from both ends equally or follow some other pattern.

Pitfall Example:

def minDifference(self, nums: List[int]) -> int:
    nums.sort()
    n = len(nums)
  
    # Wrong: Only considering removing from both ends equally
    return min(
        nums[-1] - nums[3],  # Remove 3 from left only
        nums[-4] - nums[0]   # Remove 3 from right only
    )
    # Missing cases like removing 1 from left and 2 from right

Solution: Always iterate through all 4 possible distributions (0-3, 1-2, 2-1, 3-0) to find the true minimum.