Problem Description

You are given an integer array nums. The problem defines three types of scores:

• Low score: The minimum absolute difference between any two integers in the array
• High score: The maximum absolute difference between any two integers in the array
• Score: The sum of the high score and low score

Your task is to find the minimum possible score after changing the values of exactly two elements in nums to any values you want.

For example, if nums = [1, 4, 7, 8, 5]:

• The low score would be min(|4-1|, |7-4|, |8-7|, |5-4|, ...) = 1
• The high score would be max(|8-1|, |7-1|, |5-1|, ...) = 7
• The score would be 1 + 7 = 8

After changing two elements optimally, you need to minimize this total score.

The key insight is that by changing two elements strategically, you can make the minimum difference between any two elements become 0 (by making at least two elements equal). This means the final score will just be the high score (maximum difference) after the changes, since the low score becomes 0.

The solution considers three strategies after sorting the array:

1. Change the two smallest values to match nums[2], making the range nums[n-1] - nums[2]
2. Change the smallest to match nums[1] and the largest to match nums[n-2], making the range nums[n-2] - nums[1]
3. Change the two largest values to match nums[n-3], making the range nums[n-3] - nums[0]

The answer is the minimum among these three options.

Intuition

The first key observation is that we can always make the low score (minimum difference) equal to 0 by changing at most two elements to be equal to each other. Since we're allowed to change two elements to any values, we can simply make them equal to some existing element in the array. This means the minimum difference becomes 0.

Once the low score is 0, the total score becomes just the high score (maximum difference). So our problem reduces to: minimize the maximum difference after changing two elements.

After sorting the array, the maximum difference is always nums[last] - nums[first]. To minimize this range, we need to either:

• Increase the minimum values, or
• Decrease the maximum values, or
• Do a combination of both

Since we can change exactly two elements, we have three strategic options:

1. Change both smallest elements: We effectively "remove" the two smallest values by changing them to something larger. The new range becomes from the 3rd smallest (nums[2]) to the largest (nums[n-1]), giving us nums[n-1] - nums[2].

2. Change one smallest and one largest: We "remove" one extreme from each end. The new range becomes from the 2nd smallest (nums[1]) to the 2nd largest (nums[n-2]), giving us nums[n-2] - nums[1].

3. Change both largest elements: We effectively "remove" the two largest values by changing them to something smaller. The new range becomes from the smallest (nums[0]) to the 3rd largest (nums[n-3]), giving us nums[n-3] - nums[0].

These are the only three meaningful ways to use our two changes to minimize the range. Any other strategy would be suboptimal because we wouldn't be fully utilizing our ability to eliminate extreme values.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a straightforward greedy approach after sorting:

1. Sort the array: First, we sort nums in ascending order. This allows us to easily identify the extreme values and calculate ranges efficiently. Time complexity for sorting is O(n log n).

2. Calculate three possible scenarios: After sorting, we compute the score for each of the three strategies:

   • nums[-1] - nums[2]: This represents changing the two smallest values. We're left with elements from index 2 to n-1.
   • nums[-2] - nums[1]: This represents changing one smallest and one largest value. We're left with elements from index 1 to n-2.
   • nums[-3] - nums[0]: This represents changing the two largest values. We're left with elements from index 0 to n-3.

3. Return the minimum: We take the minimum of these three values using the min() function.

The code implementation is remarkably concise:

class Solution:
    def minimizeSum(self, nums: List[int]) -> int:
        nums.sort()
        return min(nums[-1] - nums[2], nums[-2] - nums[1], nums[-3] - nums[0])

The elegance of this solution lies in its simplicity - we don't need to track which elements we're changing or what values we're changing them to. We only need to calculate what the resulting range would be after optimally removing two extreme values in each of the three possible ways.

Time Complexity: O(n log n) due to sorting, where n is the length of the array.

Space Complexity: O(log n) for the sorting algorithm's recursion stack (assuming Python's Timsort implementation).

This problem is similar to LeetCode 1509 "Minimum Difference Between Largest and Smallest Value in Three Moves", which uses the same greedy approach but allows three modifications instead of two.

Example Walkthrough

Let's walk through the solution with nums = [3, 50, 45, 1, 8]:

Step 1: Sort the array After sorting: nums = [1, 3, 8, 45, 50]

Step 2: Understand what we're doing We can change exactly 2 elements to any values. The key insight is that we can always make the minimum difference (low score) equal to 0 by making two elements equal. So our score becomes just the maximum difference (high score) after changes.

Step 3: Calculate three strategies

Strategy 1: Change the two smallest values

• We change nums[0]=1 and nums[1]=3 to any values (ideally equal to nums[2]=8)
• After changes, our effective array for calculating range is: [8, 45, 50]
• High score = 50 - 8 = 42
• Low score = 0 (since we have at least two 8's now)
• Total score = 42 + 0 = 42

Strategy 2: Change one smallest and one largest

• We change nums[0]=1 and nums[4]=50 to any values (ideally something between 3 and 45)
• After changes, our effective array for calculating range is: [3, 8, 45]
• High score = 45 - 3 = 42
• Low score = 0 (we can make the changed elements equal)
• Total score = 42 + 0 = 42

Strategy 3: Change the two largest values

• We change nums[3]=45 and nums[4]=50 to any values (ideally equal to nums[2]=8)
• After changes, our effective array for calculating range is: [1, 3, 8]
• High score = 8 - 1 = 7
• Low score = 0 (since we have at least two 8's now)
• Total score = 7 + 0 = 7

Step 4: Return the minimum

• Strategy 1: Score = 42
• Strategy 2: Score = 42
• Strategy 3: Score = 7
• Minimum score = 7

The optimal solution is to change the two largest values (45 and 50) to match an existing smaller value, resulting in a minimum score of 7.

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 is the sorting step nums.sort() which uses Timsort algorithm in Python with O(n log n) time complexity. After sorting, the code performs three array accesses and two subtraction operations followed by finding the minimum of three values, all of which take O(1) time.

Space Complexity: O(1) or O(n) depending on the sorting algorithm implementation. Python's sort() method sorts the list in-place, which typically requires O(1) auxiliary space for the sorting process itself. However, Timsort may use up to O(n) space in the worst case for its temporary merge buffer. If we consider only the additional space used by the algorithm (excluding the input), it's O(1) in the best case and O(n) in the worst case.

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

Common Pitfalls

1. Misunderstanding the Problem Statement

A critical pitfall is misinterpreting what "score" means. Many initially think they need to minimize the sum of (low score + high score) where both are calculated after changes. However, the key insight is that by changing two elements strategically, you can always make the low score = 0 by making at least two elements equal. Therefore, the problem reduces to minimizing just the high score (maximum difference).

Solution: Recognize that with two changes available, you can always create duplicate values, making the minimum difference 0. Focus solely on minimizing the maximum difference.

2. Array Length Assumption

The code assumes nums has at least 4 elements (accessing indices like nums[-3], nums[2]). If the array has fewer than 4 elements, this will cause an IndexError.

Solution: Add a length check at the beginning:

class Solution:
    def minimizeSum(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 3:
            return 0  # Can make all elements equal with 2 changes
      
        nums.sort()
        return min(nums[-1] - nums[2], nums[-2] - nums[1], nums[-3] - nums[0])

3. Not Considering All Three Strategies

Some might think only about changing the two extremes (smallest or largest) and miss the hybrid strategy of changing one from each end. This leads to suboptimal solutions.

Solution: Always evaluate all three cases:

• Remove two smallest values
• Remove two largest values
• Remove one smallest and one largest value

4. Trying to Track Actual Changes

Attempting to track which specific elements are being changed and what values they're being changed to unnecessarily complicates the solution. The problem only asks for the final score, not the transformation details.

Solution: Focus on calculating the resulting range after conceptually removing extremes, rather than implementing the actual changes.

5. Forgetting to Sort First

Without sorting, identifying which elements to change becomes complex and error-prone. The unsorted approach would require finding the k-th smallest/largest elements repeatedly.

Solution: Always sort the array first. The O(n log n) sorting cost is justified by the simplified logic it enables.