Minimum Score by Changing Two Elements

Med

#2347Time: O(N log N), dominated by the sorting algorithm.Space: O(log N) or O(N), depending on the space used by the sorting algorithm. In Java, `Arrays.sort` for primitives has an average space complexity of O(log N).

Patterns

Greedy

Algorithms

Sorting

Data structures

Array

Prompt

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.

Example 1:

Input: nums = [1,4,7,8,5]

Output: 3

Explanation:

Change nums[0] and nums[1] to be 6 so that nums becomes [6,6,7,8,5].
The low score is the minimum absolute difference: |6 - 6| = 0.
The high score is the maximum absolute difference: |8 - 5| = 3.
The sum of high and low score is 3.

Example 2:

Input: nums = [1,4,3]

Output: 0

Explanation:

Change nums[1] and nums[2] to 1 so that nums becomes [1,1,1].
The sum of maximum absolute difference and minimum absolute difference is 0.

Constraints:

3 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Approaches

3 approaches with complexity analysis and trade-offs.

A significantly more efficient approach involves sorting the array first. To minimize the difference between the maximum and minimum elements, we must alter the current extremes. After sorting, the smallest and largest elements are easy to identify. We only need to consider three strategic choices for which two elements to change: the two smallest, the two largest, or the single smallest and single largest.

Algorithm

Sort the input array nums.
Let n be the length of the array.
If n <= 3, return 0.
Calculate three potential scores:
- score1 = nums[n-1] - nums[2] (changing the two smallest).
- score2 = nums[n-3] - nums[0] (changing the two largest).
- score3 = nums[n-2] - nums[1] (changing one smallest, one largest).
Return the minimum of score1, score2, and score3.

Walkthrough

The key insight is that the high score is determined by max(nums) - min(nums). To reduce this gap, we must change either the minimum element, the maximum element, or both. With two changes available, we have a few powerful options:

Change the two smallest elements: By sorting the array, these are nums[0] and nums[1]. We can change them to match nums[2]. The new minimum becomes nums[2], and the maximum remains nums[n-1]. The new high score is nums[n-1] - nums[2].
Change the two largest elements: These are nums[n-1] and nums[n-2]. We change them to match nums[n-3]. The new maximum becomes nums[n-3], and the minimum remains nums[0]. The new high score is nums[n-3] - nums[0].
Change the smallest and the largest element: These are nums[0] and nums[n-1]. We change nums[0] to nums[1] and nums[n-1] to nums[n-2]. The new range is from nums[1] to nums[n-2]. The new high score is nums[n-2] - nums[1].

The minimum of these three resulting scores is our answer. As in the previous approach, the low score can be made 0 in each case.

1import java.util.Arrays;2 3class Solution {4    public int minimizeSum(int[] nums) {5        int n = nums.length;6        if (n <= 3) {7            return 0;8        }9 10        Arrays.sort(nums);11 12        // Case 1: Change the two smallest elements.13        // New range: nums[2] to nums[n-1]14        int score1 = nums[n - 1] - nums[2];15 16        // Case 2: Change the two largest elements.17        // New range: nums[0] to nums[n-3]18        int score2 = nums[n - 3] - nums[0];19 20        // Case 3: Change the smallest and the largest element.21        // New range: nums[1] to nums[n-2]22        int score3 = nums[n - 2] - nums[1];23 24        return Math.min(score1, Math.min(score2, score3));25    }26}

Complexity

Time

O(N log N), dominated by the sorting algorithm.

Space

O(log N) or O(N), depending on the space used by the sorting algorithm. In Java, `Arrays.sort` for primitives has an average space complexity of O(log N).

Trade-offs

Pros

Much more efficient than the brute-force approach.
The logic is clear and relatively easy to implement once the core idea is understood.

Cons

The O(N log N) time complexity is not optimal, as sorting the entire array is more work than necessary.

The most optimal solution avoids a full sort. It recognizes that we only need the three smallest and three largest elements to evaluate the three critical scenarios. These six values can be found in a single pass through the array, leading to a linear time complexity.

Algorithm

If array length n <= 3, return 0.
Initialize six variables to track the three smallest (min1, min2, min3) and three largest (max1, max2, max3) elements.
Iterate through the nums array once.
- In each iteration, update the six variables with the current number if it qualifies as one of the three smallest or largest.
After the loop, calculate the three candidate scores:
- score1 = max1 - min3
- score2 = max3 - min1
- score3 = max2 - min2
Return the minimum of the three scores.

Walkthrough

This approach refines the sorting-based method. Instead of sorting the entire O(N log N) operation, we can find the required elements—the three smallest and three largest—in O(N) time. We can iterate through the array just once, keeping track of the top three and bottom three values seen so far.

After one pass, we will have identified:

min1, min2, min3: The three smallest elements.
max1, max2, max3: The three largest elements.

These correspond to nums[0], nums[1], nums[2] and nums[n-3], nums[n-2], nums[n-1] in the sorted version of the array. We can then compute the same three candidate scores as in the sorting approach:

max1 - min3 (corresponds to nums[n-1] - nums[2])
max3 - min1 (corresponds to nums[n-3] - nums[0])
max2 - min2 (corresponds to nums[n-2] - nums[1])

The minimum of these three is the final answer.

1class Solution {2    public int minimizeSum(int[] nums) {3        int n = nums.length;4        if (n <= 3) {5            return 0;6        }7 8        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE, min3 = Integer.MAX_VALUE;9        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;10 11        for (int num : nums) {12            // Update three smallest13            if (num <= min1) {14                min3 = min2;15                min2 = min1;16                min1 = num;17            } else if (num <= min2) {18                min3 = min2;19                min2 = num;20            } else if (num <= min3) {21                min3 = num;22            }23 24            // Update three largest25            if (num >= max1) {26                max3 = max2;27                max2 = max1;28                max1 = num;29            } else if (num >= max2) {30                max3 = max2;31                max2 = num;32            } else if (num >= max3) {33                max3 = num;34            }35        }36 37        // Case 1: Change two smallest (min1, min2). New range is max1 - min3.38        int score1 = max1 - min3;39        // Case 2: Change two largest (max1, max2). New range is max3 - min1.40        int score2 = max3 - min1;41        // Case 3: Change smallest and largest (min1, max1). New range is max2 - min2.42        int score3 = max2 - min2;43 44        return Math.min(score1, Math.min(score2, score3));45    }46}

Complexity

Time

O(N), as we only need to iterate through the array a single time.

Space

O(1), as we only use a constant number of variables regardless of the input size.

Trade-offs

Pros

Achieves the best possible time complexity.
Uses constant extra space.

Cons

The implementation logic for tracking the six extreme values in one pass is slightly more complex than the other approaches.

This approach exhaustively checks every possible pair of elements to change. For each pair, it calculates the potential minimum high score by finding the range (maximum - minimum) of the remaining elements. The overall minimum score is the minimum of these ranges. This method is straightforward but computationally expensive.

Algorithm

Initialize minScore to infinity.
Iterate through all pairs of indices (i, j) where i < j.
- Inside the loop, find the minimum (minVal) and maximum (maxVal) of the elements in nums excluding nums[i] and nums[j].
- Calculate the difference diff = maxVal - minVal.
- Update minScore = min(minScore, diff).
Return minScore.

Walkthrough

The core idea is that we can change any two elements. To minimize the score, we should aim to make the low score zero and the high score as small as possible. The low score can be made zero by changing the two elements to the same value. To minimize the high score (the range of the array), we should change the two elements to values that fall within the range of the other n-2 elements. This means the new range is simply the range of the n-2 elements that were not changed.

This leads to a brute-force algorithm where we simulate 'removing' every possible pair of elements and finding the range of what's left.

Here is the algorithm:

Initialize a variable minScore to a very large value.
Use nested loops to iterate through all unique pairs of indices (i, j) in the nums array.
For each pair, find the minimum and maximum values among the other n-2 elements (i.e., all elements at index k where k != i and k != j).
Calculate the difference currentScore = maxVal - minVal.
Update minScore = Math.min(minScore, currentScore).
After all pairs have been checked, minScore will hold the minimum possible high score, which is our answer.

1class Solution {2    public int minimizeSum(int[] nums) {3        int n = nums.length;4        if (n <= 3) {5            return 0;6        }7 8        int minScore = Integer.MAX_VALUE;9 10        for (int i = 0; i < n; i++) {11            for (int j = i + 1; j < n; j++) {12                int currentMin = Integer.MAX_VALUE;13                int currentMax = Integer.MIN_VALUE;14 15                for (int k = 0; k < n; k++) {16                    if (k == i || k == j) {17                        continue;18                    }19                    currentMin = Math.min(currentMin, nums[k]);20                    currentMax = Math.max(currentMax, nums[k]);21                }22                minScore = Math.min(minScore, currentMax - currentMin);23            }24        }25        return minScore;26    }27}

Complexity

Time

O(N<sup>3</sup>), where N is the number of elements in `nums`. There are O(N<sup>2</sup>) pairs of elements to 'remove', and for each pair, we iterate through the remaining O(N) elements to find the new min and max.

Space

O(1), as we only use a few variables to store the intermediate min/max and the result. No extra data structures are needed.

Trade-offs

Pros

Conceptually simple and easy to understand.
Guaranteed to find the correct answer by checking all possibilities of removing two elements.

Cons

Extremely inefficient with a cubic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.

Solutions

Solution

1class Solution {2public3  int minimizeSum(int[] nums) {4    Arrays.sort(nums);5    int n = nums.length;6    int a = nums[n - 1] - nums[2];7    int b = nums[n - 2] - nums[1];8    int c = nums[n - 3] - nums[0];9    return Math.min(a, Math.min(b, c));10  }11}

1class Solution {2public:3  int minimizeSum(vector<int> &nums) {4    sort(nums.begin(), nums.end());5    int n = nums.size();6    return min(7        {nums[n - 1] - nums[2], nums[n - 2] - nums[1], nums[n - 3] - nums[0]});8  }9};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int minimizeSum(int[] nums) {4    Arrays.sort(nums);5    int n = nums.length;6    int a = nums[n - 1] - nums[2];7    int b = nums[n - 2] - nums[1];8    int c = nums[n - 3] - nums[0];9    return Math.min(a, Math.min(b, c));10  }11}

1class Solution {2public:3  int minimizeSum(vector<int> &nums) {4    sort(nums.begin(), nums.end());5    int n = nums.size();6    return min(7        {nums[n - 1] - nums[2], nums[n - 2] - nums[1], nums[n - 3] - nums[0]});8  }9};

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

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.