# Minimum Score by Changing Two Elements
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-score-by-changing-two-elements)
Canonical: https://scaleengineer.com/dsa/problems/minimum-score-by-changing-two-elements
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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`.

**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 <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Brute Force by Removing Two Elements
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.
**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.
**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.
### Explanation
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:
1. Initialize a variable `minScore` to a very large value.
2. Use nested loops to iterate through all unique pairs of indices `(i, j)` in the `nums` array.
3. 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`).
4. Calculate the difference `currentScore = maxVal - minVal`.
5. Update `minScore = Math.min(minScore, currentScore)`.
6. After all pairs have been checked, `minScore` will hold the minimum possible high score, which is our answer.

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

        int minScore = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int currentMin = Integer.MAX_VALUE;
                int currentMax = Integer.MIN_VALUE;

                for (int k = 0; k < n; k++) {
                    if (k == i || k == j) {
                        continue;
                    }
                    currentMin = Math.min(currentMin, nums[k]);
                    currentMax = Math.max(currentMax, nums[k]);
                }
                minScore = Math.min(minScore, currentMax - currentMin);
            }
        }
        return minScore;
    }
}
```
### 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`.

## 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.
**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).
**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.
### Explanation
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:

1.  **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]`.
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]`.
3.  **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.

```java
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));
    }
}
```
### 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`.

## Optimal Single Pass Approach
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.
**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.
**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.
### Explanation
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.

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

        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE, min3 = Integer.MAX_VALUE;
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;

        for (int num : nums) {
            // Update three smallest
            if (num <= min1) {
                min3 = min2;
                min2 = min1;
                min1 = num;
            } else if (num <= min2) {
                min3 = min2;
                min2 = num;
            } else if (num <= min3) {
                min3 = num;
            }

            // Update three largest
            if (num >= max1) {
                max3 = max2;
                max2 = max1;
                max1 = num;
            } else if (num >= max2) {
                max3 = max2;
                max2 = num;
            } else if (num >= max3) {
                max3 = num;
            }
        }

        // Case 1: Change two smallest (min1, min2). New range is max1 - min3.
        int score1 = max1 - min3;
        // Case 2: Change two largest (max1, max2). New range is max3 - min1.
        int score2 = max3 - min1;
        // Case 3: Change smallest and largest (min1, max1). New range is max2 - min2.
        int score3 = max2 - min2;

        return Math.min(score1, Math.min(score2, score3));
    }
}
```
### 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.

# Solutions
### Java

```java
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));
  }
}

```

### CPP

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

```

### Python

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

```