Minimum Score by Changing Two Elements

MEDIUM

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.

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

Checkout 3 different approaches to solve Minimum Score by Changing Two Elements. Click on different approaches to view the approach and algorithm in detail.

Sorting and Checking Candidates

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.

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.

import java.util.Arrays;

class Solution {
    public int minimizeSum(int[] nums) {
        int n = nums.length;
        if (n <= 3) {
            return 0;
        }

        Arrays.sort(nums);

        // Case 1: Change the two smallest elements.
        // New range: nums[2] to nums[n-1]
        int score1 = nums[n - 1] - nums[2];

        // Case 2: Change the two largest elements.
        // New range: nums[0] to nums[n-3]
        int score2 = nums[n - 3] - nums[0];

        // Case 3: Change the smallest and the largest element.
        // New range: nums[1] to nums[n-2]
        int score3 = nums[n - 2] - nums[1];

        return Math.min(score1, Math.min(score2, score3));
    }
}

Complexity Analysis

Time Complexity: O(N log N), dominated by the sorting algorithm.Space Complexity: 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).

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Minimum Score by Changing Two Elements. Click on different languages to view the code.

class Solution {
public
  int minimizeSum(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    int a = nums[n - 1] - nums[2];
    int b = nums[n - 2] - nums[1];
    int c = nums[n - 3] - nums[0];
    return Math.min(a, Math.min(b, c));
  }
}

Video Solution

Watch the video walkthrough for Minimum Score by Changing Two Elements

Algorithms:

Sorting

Patterns:

Greedy

Data Structures:

Array