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

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

Solution

The foundation of the idea:

If 3 changes(moves) on any of the element is allowed, there are only 4 choice for us to let the (maxElement - minElment) is minimum, thus, for each case, the results are shown as below

• change the 3 biggest elements to some value which doest affect the result

  • the result will be (4thMax - 1stMin)

• change the 2 biggest elements and 1 smallest

  • the result will be (3rdMax - 2ndMin)

• change the 1 biggest element, and the 2 smallest elements

  • the result will be (2ndMax - 3rdMin)

• change the 3 smallest elements

  • the result will be (1stMax - 4thMin)

So, if we can get the 1st~4th Max and Min value, we got all possible results. We just need to find the minimum among them.

public int minDifference(int[] nums){
    if(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-1-3+i] - nums[i]);
    }
    return;
}

Time Complexity: O(nlogn)

Enhancement:

Actually, we don't need to sort the array, we just need to find the 4 largest and smallest elements among them.

We can use max/min-heap to deal with it.

Time Complexity: O(nlogk), where k is how many moves

public int minDifference(int[] nums){

    if(nums.length <= 4) return 0;
    PriorityQueue<Integer> maxValues = new PriorityQueue<>(); 
    PriorityQueue<Integer> minValues = new PriorityQueue<>((a,b)-> Integer.compare(b,a));
    for(int num : nums) {
        maxValues.add(num);
        minValues .add(num);
        
        if(maxValues.size() > 4){
            maxValues.poll();
            minValues.poll();
        }
    }
    
    int[] minSeq = new int[] {minValues.poll(), minValues.poll(), minValues.poll(), minValues.poll()};
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < 4; i++) {
        min = Math.min(min, maxValues.poll() - minSeq[3-i]);    
    }
    return min;

}