Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

1
2
3
4
5
6
7
8
9


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^5
  • 1 <= nums[i] <= 10^9

Solution

Method 1 – Greedy + Sorting

Intuition

To minimize the score after changing two elements, we can change the two largest or two smallest elements to match others. The minimum score is the minimum among three options:

  1. Change two smallest elements.
  2. Change two largest elements.
  3. Change one smallest and one largest element.

Approach

Sort the array. The minimum score is min of:

  • (nums[n-1] - nums[2]) + (nums[1] - nums[0])
  • (nums[n-3] - nums[0]) + (nums[1] - nums[0])
  • (nums[n-1] - nums[0]) + (nums[2] - nums[1]) But since low score is always 0 after changing two elements to be equal, the score is just the difference between the remaining max and min. So, answer is min(nums[n-1]-nums[2], nums[n-3]-nums[0], nums[n-2]-nums[1]).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

import "sort"
func minimizeSum(nums []int) int {
    sort.Ints(nums)
    n := len(nums)
    a := nums[n-1]-nums[2]
    b := nums[n-3]-nums[0]
    c := nums[n-2]-nums[1]
    if a < b && a < c { return a }
    if b < c { return b }
    return c
}
1
2
3
4
5
6
7
8

import java.util.*;
class Solution {
    public int minimizeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return Math.min(nums[n-1]-nums[2], Math.min(nums[n-3]-nums[0], nums[n-2]-nums[1]));
    }
}
1
2
3
4
5
6
7

class Solution {
    fun minimizeSum(nums: IntArray): Int {
        nums.sort()
        val n = nums.size
        return minOf(nums[n-1]-nums[2], nums[n-3]-nums[0], nums[n-2]-nums[1])
    }
}
1
2
3
4
5

class Solution:
    def minimizeSum(self, nums: list[int]) -> int:
        nums.sort()
        n = len(nums)
        return min(nums[n-1]-nums[2], nums[n-3]-nums[0], nums[n-2]-nums[1])
1
2
3
4
5
6
7

impl Solution {
    pub fn minimize_sum(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        let n = nums.len();
        *[nums[n-1]-nums[2], nums[n-3]-nums[0], nums[n-2]-nums[1]].iter().min().unwrap()
    }
}
1
2
3
4
5
6
7

class Solution {
    minimizeSum(nums: number[]): number {
        nums.sort((a,b)=>a-b);
        const n = nums.length;
        return Math.min(nums[n-1]-nums[2], nums[n-3]-nums[0], nums[n-2]-nums[1]);
    }
}

Complexity

  • ⏰ Time complexity: O(n log n) — For sorting.
  • 🧺 Space complexity: O(1) — In-place sort.