> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/1509-minimum-difference-between-largest-and-smallest-value-in-three-moves.md).

# 1509. Minimum Difference Between Largest and Smallest Value in Three Moves

<https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves>

## Description

Given an array `nums`, you are allowed to choose one element of `nums` and change it by any value in one move.

Return the minimum difference between the largest and smallest value of `nums` after perfoming at most 3 moves.

**Example 1:**

```
**Input:** nums = [5,3,2,4]
**Output:** 0
**Explanation:** Change the array [5,3,2,4] to [**2**,**2**,2,**2**].
The difference between the maximum and minimum is 2-2 = 0.
```

**Example 2:**

```
**Input:** nums = [1,5,0,10,14]
**Output:** 1
**Explanation:** Change the array [1,5,0,10,14] to [1,**1**,0,**1**,**1**]. 
The difference between the maximum and minimum is 1-0 = 1.
```

**Example 3:**

```
**Input:** nums = [6,6,0,1,1,4,6]
**Output:** 2
```

**Example 4:**

```
**Input:** nums = [1,5,6,14,15]
**Output:** 1
```

**Constraints:**

* `1 <= nums.length <= 10^5`
* `-10^9 <= nums[i] <= 10^9`

## ac1: PriorityQueue

The idea is we have 4 options: in a sorted array, remove 1) 0 min, 3 max; 2) 1 min, 2 max; 3) 2 min, 1 max; 4) 3 min, 0 max. Get 4 min + 4 max via 2 PriorityQueue.

```java
class Solution {
    public int minDifference(int[] nums) {
        if (nums == null || nums.length <= 4) {
            return 0;
        }
        
        int[] arr = getMinMaxArray(nums);
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < 4; i++) {
            min = Math.min(min, arr[4+i] - arr[i]);
        }
        
        return min;
    }
    
    private int[] getMinMaxArray(int[] nums) {
        PriorityQueue<Integer> min = new PriorityQueue<>();
        PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
        for (int n : nums) {
            min.offer(n);
            if (min.size() > 4) min.poll();
            max.offer(n);
            if (max.size() > 4) max.poll();
        }
        return queueToArray(min, max);
    }
    
    private int[] queueToArray(PriorityQueue<Integer> min, PriorityQueue<Integer> max) {
        int[] arr = new int[8];
        int i = 3;
        while (!max.isEmpty()) {
            arr[i--] = max.poll();
        }
        i = 4;
        while (!min.isEmpty()) {
            arr[i++] = min.poll();
        }
        return arr;
    }
}
// O(N) time, O(1) space. 
```

## ac2: Sorting

```java
class Solution {
    public int minDifference(int[] nums) {
        if (nums == null || nums.length <= 4) {
            return 0;
        }
        
        Arrays.sort(nums);
        
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < 4; i++) {
            min = Math.min(min, nums[nums.length-4+i] - nums[i]);
        }
        
        return min;
    }
}
// O(NlogN) time, O(1) space. 
```