Minimum Score by Changing Two Elements

Problem Description

You are given an integer array nums. The low score of nums is the minimum absolute difference between any two integers. The high score of nums is the maximum absolute difference between any two integers. The score of nums is the sum of the high and low scores. Return the minimum score after changing two elements of nums.

Key Insights

• The low score can be minimized to zero by making at least two elements equal.
• The high score depends on the maximum and minimum values in the array and can be adjusted by changing two elements.
• Changing two elements allows us to strategically pick new values to minimize the score efficiently.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array to find minimum and maximum values effectively.
Space Complexity: O(1) - no additional space is used apart from input storage.

Solution

To solve this problem, we can follow these steps:

1. Sort the array to easily access the minimum and maximum values.
2. Calculate the original low and high scores.
3. Consider changing the two smallest elements to the value of the third smallest element, and changing the two largest elements to the value of the third largest element.
4. Calculate the new scores after these changes and return the minimum score.

Code Solutions