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] <= 109The idea is to sort the array and find the minimal difference after removing at most three elements from either side. By sorting the array, you can easily identify the largest and smallest values that might stay in the array. After sorting, the array becomes an ordered sequence, allowing you to attempt minimizing differences by changing elements from the edges.
This approach essentially checks the possible combinations of keeping n - 3 elements and removing the smallest, or the largest, or a mix of both.
This Python solution first checks if the array length is less than or equal to 4, in which case the result is 0 because we can change all elements in at most 3 moves. It then sorts the array and calculates the minimal difference by considering four potential scenarios: removing either the largest three, the smallest three, or combinations thereof.
C
C++
Java
C#
JavaScript
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) since the sorting is in-place.
Minimum Difference Between Highest and Lowest of K Scores - Leetcode Weekly Contest - 1984 Python • NeetCode • 19,321 views views
Watch 9 more video solutions →Practice Minimum Difference Between Largest and Smallest Value in Three Moves with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor