1509

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

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

Related Topics:
Array, Sort

Solution 1. Sort

Sort the array, then we can remove i numbers from the front of the array and 3 - i numbers from the rear of the array, 0 <= i <= 3.

The answer is max( A[N - 4 + i] - A[i] | 0 <= i <= 3 ).

// OJ: https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int minDifference(vector<int>& A) {
        if (A.size() <= 3) return 0;
        sort(begin(A), end(A));
        int ans = INT_MAX, N = A.size();
        for (int i = 0; i <= 3; ++i) {
            ans = min(ans, A[N - 4 + i] - A[i]);
        }
        return ans;
    }
};