Minimum Score by Changing Two Elements

Intuitionthe low score can disappear, so only the untouched range matters

Sort the array so its minimum and maximum are visible. After changing two elements, set those two changed values equal to each other and place them inside the range of the untouched elements. Their low score is then zero, and they do not enlarge the high score. The resulting score is simply the difference between the largest and smallest untouched values.

The only question is which two sorted elements to remove from the untouched range. Removing an interior element cannot change either endpoint, so an optimal choice removes elements from the two ends: both smallest, both largest, or one smallest and one largest. Each choice leaves a specific interval, and the smallest interval is the answer.

Approach

1. 1Let n be the array length and return 0 immediately when n <= 3, because after changing two elements at most one original value remains and both changed values can be made equal to it.
2. 2Sort nums so equal-position choices describe the smallest and largest untouched values; without sorting, the three endpoint cases cannot be read from fixed indices.
3. 3Consider changing the two largest values, leaving nums[0] through nums[n - 2] untouched. Their range is nums[n - 2] - nums[0], and the changed values can be set equal without increasing that range.
4. 4Consider changing the two smallest values, leaving nums[1] through nums[n - 1] untouched. Their range is nums[n - 1] - nums[1], which covers the opposite endpoint choice.
5. 5Consider changing one smallest and one largest value, leaving nums[1] through nums[n - 2] untouched. Their range is nums[n - 2] - nums[1], and this is the third possible way to remove two endpoints.
6. 6Return the minimum of the three ranges, because each candidate already has low score zero and therefore its range is its complete score.

Complexitysorting dominates the scan

Annotated solutionC++ · sort in place · three endpoint candidates

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    int minimizeSum(vector<int>& nums) {
        int n = nums.size();
        if (n <= 3) {
            return 0;
        }

        sort(nums.begin(), nums.end());

        int changeLargest = nums[n - 2] - nums[0];
        int changeSmallest = nums[n - 1] - nums[1];
        int changeBothEnds = nums[n - 2] - nums[1];

        return min({changeLargest, changeSmallest, changeBothEnds});
    }
};

The three expressions are ranges of untouched values, not scores that still need another low-score term. In every case, the two changed values are made equal, so the low score is zero. The special case n <= 3 must come before these formulas because their index ranges assume at least two untouched values.

Common mistakestwo wrong shapes that look plausible