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] <= 109Problem Overview: You can change the value of any element in the array in one move. After at most three moves, minimize the difference between the largest and smallest values. The goal is to determine the smallest possible max(nums) - min(nums) after performing up to three modifications.
Key Insight: Changing a number to any value effectively removes its influence on the minimum or maximum. With three moves, you can eliminate up to three extreme values from either end of the sorted array. After sorting, only four meaningful scenarios exist: remove the three largest values, remove two largest and one smallest, remove one largest and two smallest, or remove the three smallest values.
Approach 1: Brute Force Extremes Simulation (O(n log n) time, O(1) extra space)
Sort the array, then simulate removing combinations of up to three elements from either end. For each possible combination, compute the difference between the remaining smallest and largest values. There are only four valid configurations because the total removed elements must equal three. This approach works because modifying a number can make it irrelevant to the min/max range. Sorting dominates the runtime with O(n log n) time.
Approach 2: Sorting and Window Analysis (O(n log n) time, O(1) space)
Sort the array and observe that the final range must come from a window of length n - 3. Evaluate four candidate windows: [0, n-4], [1, n-3], [2, n-2], and [3, n-1]. Each represents replacing three elements outside the window. Compute the difference between the last and first element in each window and take the minimum. The operation is simple: sort, iterate over four windows, and track the minimum difference.
This solution combines ideas from Sorting and Greedy reasoning. Sorting exposes the extremes, and the greedy observation limits the solution space to four possibilities. The input array itself is the only major data structure involved, making it a classic Array optimization problem.
Recommended for interviews: The sorting + window analysis approach is what interviewers expect. It shows you recognize that three moves only affect the array's extremes and reduces the search space to four deterministic cases. Brute force reasoning helps demonstrate understanding, but the greedy observation and constant-case evaluation signal strong problem-solving skills.
The 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.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) since the sorting is in-place.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Sorting and Window Analysis | Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) since the sorting is in-place. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Extremes Simulation | O(n log n) | O(1) | When first reasoning about the problem and validating the four possible removal scenarios |
| Sorting and Window Analysis (Optimal) | O(n log n) | O(1) | Best general solution; evaluate four windows after sorting |
| Min/Max Heap Tracking | O(n log k) | O(k) | Useful when only the smallest and largest few elements are required without fully sorting |
Minimum Difference Between Largest and Smallest Value in Three Moves - Leetcode 1509 - Python • NeetCodeIO • 13,613 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