# Minimum Difference Between Largest and Smallest Value in Three Moves
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves)
Canonical: https://scaleengineer.com/dsa/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves
**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`.

In one move, you can choose one element of `nums` and change it to **any value**.

Return _the minimum difference between the largest and smallest value of `nums` **after performing at most three moves**_.

**Example 1:**

**Input:** nums = [5,3,2,4]
**Output:** 0
**Explanation:** We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

**Example 2:**

**Input:** nums = [1,5,0,10,14]
**Output:** 1
**Explanation:** We can make at most 3 moves.
In the first move, change 5 to 0. nums becomes [1,0,0,10,14].
In the second move, change 10 to 0. nums becomes [1,0,0,0,14].
In the third move, change 14 to 1. nums becomes [1,0,0,0,1].
After performing 3 moves, the difference between the minimum and maximum is 1 - 0 = 1.
It can be shown that there is no way to make the difference 0 in 3 moves.

**Example 3:**

**Input:** nums = [3,100,20]
**Output:** 0
**Explanation:** We can make at most 3 moves.
In the first move, change 100 to 7. nums becomes [3,7,20].
In the second move, change 20 to 7. nums becomes [3,7,7].
In the third move, change 3 to 7. nums becomes [7,7,7].
After performing 3 moves, the difference between the minimum and maximum is 7 - 7 = 0.

**Constraints:**

* `1 <= nums.length <= 105`
* `-109 <= nums[i] <= 109`

# Approaches
## Sorting Approach
The core idea is that to minimize the difference between the largest and smallest values, we should use our three moves to alter the existing smallest and largest values in the array. By sorting the array, we can easily identify these extreme values. Once the array is sorted, the problem is reduced to finding the minimum range among four possible scenarios that arise from 'removing' three elements from the extremes.
**Time:** O(N log N), where N is the number of elements in `nums`. This is dominated by the sorting step. · **Space:** O(log N) or O(N), depending on the implementation of the sorting algorithm. For instance, Java's `Arrays.sort` for primitives uses a variant of Quicksort which requires O(log N) space on average for the recursion stack.
**Pros:** Conceptually simple and straightforward to implement.; The logic directly follows from the core insight of the problem after sorting.
**Cons:** The time complexity is dominated by the sorting step, which is not optimal as a full sort is not strictly required.
### Explanation
This approach leverages sorting to simplify the problem. When an element's value is changed, it can be set to any other value. To minimize the difference between the maximum and minimum, we should change the values of the outliers—the largest and smallest numbers. By changing an element, we effectively remove it from being a candidate for the minimum or maximum of the array.

With three moves, we can change three elements. The optimal strategy is to use these moves on the smallest and/or largest elements. After sorting the array `nums`, we have a clear view of these extremes. The four scenarios correspond to how we distribute our three 'removals' between the low and high ends of the sorted array. We calculate the resulting difference for each scenario and take the minimum.

For example, if we change the two largest elements and one smallest element, the new maximum will be the third-largest element of the original array, and the new minimum will be the second-smallest. The difference is then `nums[n-3] - nums[1]`.

```java
import java.util.Arrays;

class Solution {
    public int minDifference(int[] nums) {
        int n = nums.length;
        if (n <= 4) {
            return 0;
        }
        
        Arrays.sort(nums);
        
        // Case 1: Change 3 largest elements
        int diff1 = nums[n - 4] - nums[0];
        
        // Case 2: Change 2 largest and 1 smallest
        int diff2 = nums[n - 3] - nums[1];
        
        // Case 3: Change 1 largest and 2 smallest
        int diff3 = nums[n - 2] - nums[2];
        
        // Case 4: Change 3 smallest elements
        int diff4 = nums[n - 1] - nums[3];
        
        return Math.min(Math.min(diff1, diff2), Math.min(diff3, diff4));
    }
}
```
### Algorithm
- If the length of the input array `nums` is 4 or less, we can make all elements equal in at most 3 moves. Thus, the minimum difference is 0.
- Sort the array `nums` in non-decreasing order. Let the size of the array be `n`.
- After sorting, the smallest elements are at the beginning and the largest elements are at the end.
- We have four possible strategies to use our three moves to minimize the range (`max - min`):
  1. Change the three largest elements. The new range will be between `nums[0]` and `nums[n-4]`. Difference: `nums[n-4] - nums[0]`.
  2. Change the two largest and one smallest element. The new range will be between `nums[1]` and `nums[n-3]`. Difference: `nums[n-3] - nums[1]`.
  3. Change one largest and two smallest elements. The new range will be between `nums[2]` and `nums[n-2]`. Difference: `nums[n-2] - nums[2]`.
  4. Change the three smallest elements. The new range will be between `nums[3]` and `nums[n-1]`. Difference: `nums[n-1] - nums[3]`.
- The final answer is the minimum of these four calculated differences.

## Linear Scan with Heaps
This approach improves upon the sorting method by recognizing that we don't need the entire array to be sorted. We only need to know the four smallest and four largest elements to compute the four candidate differences. These can be found in linear time, `O(N)`, without the overhead of a full sort, making this approach more efficient for large inputs.
**Time:** O(N log K), where N is the number of elements and K is 4. Since K is a constant, the complexity is O(N). Each insertion/deletion in a heap of size 4 takes O(log 4) time, which is constant. · **Space:** O(1), as the priority queues used to store the smallest and largest elements have a constant size (4).
**Pros:** Optimal time complexity of O(N).; Efficient for very large arrays as it avoids a full sort.
**Cons:** The implementation is more complex than the sorting approach, involving data structures like priority queues.; Requires careful handling of heap properties and extraction of elements to match them to the correct scenarios.
### Explanation
Instead of an `O(N log N)` sort, we can find the four smallest and four largest elements in a single `O(N)` pass. A clean way to do this is by using two priority queues (heaps).

1.  A **max-heap** of size 4 is used to keep track of the four smallest elements. When a new element is considered, it's added to the heap. If the heap size becomes 5, the largest element is removed. At the end, the heap contains the four smallest elements of the entire array.
2.  A **min-heap** of size 4 is used similarly to track the four largest elements. If its size exceeds 4, the smallest element is removed.

After iterating through the array, we have the four smallest and four largest elements. Let's call them `s1, s2, s3, s4` (in increasing order) and `l1, l2, l3, l4` (where `l1` is the 4th largest and `l4` is the largest). The four scenarios for the minimum difference are:
- `l1 - s1` (removing 3 largest)
- `l2 - s2` (removing 2 largest, 1 smallest)
- `l3 - s3` (removing 1 largest, 2 smallest)
- `l4 - s4` (removing 3 smallest)

The minimum of these values is the answer.

```java
import java.util.PriorityQueue;
import java.util.Collections;
import java.util.Arrays;

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

        // Max-heap to find the 4 smallest elements
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        // Min-heap to find the 4 largest elements
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            maxHeap.offer(num);
            if (maxHeap.size() > 4) {
                maxHeap.poll();
            }
            minHeap.offer(num);
            if (minHeap.size() > 4) {
                minHeap.poll();
            }
        }

        int[] smallestFour = new int[4];
        for (int i = 3; i >= 0; i--) {
            smallestFour[i] = maxHeap.poll();
        }

        int[] largestFour = new int[4];
        for (int i = 0; i < 4; i++) {
            largestFour[i] = minHeap.poll();
        }

        int minDiff = Integer.MAX_VALUE;
        // The 4 scenarios correspond to pairing the i-th smallest with the i-th largest
        // from our selected groups.
        for (int i = 0; i < 4; i++) {
            minDiff = Math.min(minDiff, largestFour[i] - smallestFour[i]);
        }
        
        return minDiff;
    }
}
```
### Algorithm
- If the length of `nums` is 4 or less, return 0.
- We need to find the four smallest and four largest elements of the array. This can be done in a single pass.
- Use two priority queues (heaps): a max-heap to keep track of the four smallest elements seen so far, and a min-heap for the four largest.
- Iterate through the input array `nums`. For each number, offer it to both heaps. If a heap's size exceeds 4, poll an element (the largest from the max-heap, the smallest from the min-heap).
- After the pass, extract the elements from the heaps into two sorted arrays: `smallestFour` and `largestFour`.
- `smallestFour[i]` will be the (i+1)-th smallest element, and `largestFour[i]` will be the (i+1)-th largest element from the end (e.g., `largestFour[0]` is the 4th largest).
- Calculate the four candidate differences: `largestFour[i] - smallestFour[i]` for `i` from 0 to 3.
- Return the minimum among these differences.

# Solutions
### Java

```java
class Solution { public int minDifference ( int [] nums ) { int n = nums . length ; if ( n < 5 ) { return 0 ; } Arrays . sort ( nums ); long ans = 1L << 60 ; for ( int l = 0 ; l <= 3 ; ++ l ) { int r = 3 - l ; ans = Math . min ( ans , ( long ) nums [ n - 1 - r ] - nums [ l ]); } return ( int ) ans ; } }
```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var minDifference =
  function (nums) {
    if (nums.length < 5) {
      return 0;
    }
    nums.sort((a, b) => a - b);
    let ans = Number.POSITIVE_INFINITY;
    for (let i = 0; i < 4; i++) {
      ans = Math.min(ans, nums.at(i - 4) - nums[i]);
    }
    return ans;
  };

```

### CPP

```cpp
class Solution { public: int minDifference ( vector < int >& nums ) { int n = nums . size (); if ( n < 5 ) { return 0 ; } sort ( nums . begin (), nums . end ()); long long ans = 1L << 60 ; for ( int l = 0 ; l <= 3 ; ++ l ) { int r = 3 - l ; ans = min ( ans , 1LL * nums [ n - 1 - r ] - nums [ l ]); } return ans ; } };
```

### Python

```python
class Solution : def minDifference ( self , nums : List [ int ]) -> int : n = len ( nums ) if n < 5 : return 0 nums . sort () ans = inf for l in range ( 4 ): r = 3 - l ans = min ( ans , nums [ n - 1 - r ] - nums [ l ]) return ans
```