Minimum Difference Between Largest and Smallest Value in Three Moves solution and explanation
Google
9 more videos on this problem
Minimum Difference Between Largest and Smallest Value in Three Moves - Leetcode 1509 - PythonNeetCodeIO · 14:31 · 13K views
Minimum Difference Between Largest and Smallest Value in Three Moves | 2 Approaches | Leetcode 1509codestorywithMIK · 31:36 · 8K views
1509. Minimum Difference Between Largest and Smallest Value in Three Moves | Heap | Sorting | GreedyAryan Mittal · 14:30 · 6K views
Google Coding Interview Question | Leetcode 1509 | Min Diff Between Max and Min Value in Three MovesWorkWithGoogler · 12:45 · 3K views
1509. Minimum Difference Between Largest and Smallest Value in Three MovesChhavi Bansal · 13:20 · 1K views
1509. Minimum Difference Between Largest and Smallest Value in Three Moves (Leetcode Medium)Programming Live with Larry · 10:06 · 1K views
1509. Minimum Difference Between Largest and Smallest Value in Three Moves | Leetcode Daily 3/7/2024AlgorithmHQ · 8:44 · 836 views
LeetCode 1509 | Minimum Difference Between Largest and Smallest Value in Three Moves | #arrays #dsaAlgo Horizon · 21:06 · 489 views
Leetcode 1509. Minimum Difference Between Largest and Smallest Value in Three MovesElite Code · 30:28 · 328 views
Minimum Difference Between Largest and Smallest Value in Three Moves [Python] [LC 1509]Todd Chaney · 10:00 · 142 views
The problem
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] <= 109
Approach overview
Problem 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.
Approach 1: Sorting and Window Analysis
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.
def minDifference(nums):
if len(nums) <= 4:
return 0
nums.sort()
return min(nums[-1] - nums[3], nums[-2] - nums[2], nums[-3] - nums[1], nums[-4] - nums[0])
# Example usage
nums1 = [5, 3, 2, 4]
nums2 = [1, 5, 0, 10, 14]
nums3 = [3, 100, 20]
print(minDifference(nums1)) # Output: 0
print(minDifference(nums2)) # Output: 1
print(minDifference(nums3)) # Output: 0import java.util.Arrays;
public class MinDifference {
public static int minDifference(int[] nums) {
if (nums.length <= 4) return 0;
Arrays.sort(nums);
return Math.min(
Math.min(nums[nums.length - 1] - nums[3], nums[nums.length - 2] - nums[2]),
Math.min(nums[nums.length - 3] - nums[1], nums[nums.length - 4] - nums[0])
);
}
public static void main(String[] args) {
int[] nums1 = {5, 3, 2, 4};
int[] nums2 = {1, 5, 0, 10, 14};
int[] nums3 = {3, 100, 20};
System.out.println(minDifference(nums1)); // Output: 0
System.out.println(minDifference(nums2)); // Output: 1
System.out.println(minDifference(nums3)); // Output: 0
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minDifference(vector<int>& nums) {
if (nums.size() <= 4) return 0;
sort(nums.begin(), nums.end());
int n = nums.size();
return min({nums[n - 1] - nums[3], nums[n - 2] - nums[2], nums[n - 3] - nums[1], nums[n - 4] - nums[0]});
}
// Example usage
int main() {
vector<int> nums1 = {5, 3, 2, 4};
vector<int> nums2 = {1, 5, 0, 10, 14};
vector<int> nums3 = {3, 100, 20};
cout << minDifference(nums1) << endl; // Output: 0
cout << minDifference(nums2) << endl; // Output: 1
cout << minDifference(nums3) << endl; // Output: 0
return 0;
}function minDifference(nums) {
if (nums.length <= 4) return 0;
nums.sort((a, b) => a - b);
return Math.min(
nums[nums.length - 1] - nums[3],
nums[nums.length - 2] - nums[2],
nums[nums.length - 3] - nums[1],
nums[nums.length - 4] - nums[0]
);
}
// Example usage
console.log(minDifference([5, 3, 2, 4])); // Output: 0
console.log(minDifference([1, 5, 0, 10, 14])); // Output: 1
console.log(minDifference([3, 100, 20])); // Output: 0#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int minDifference(int* nums, int numsSize) {
if (numsSize <= 4) return 0;
qsort(nums, numsSize, sizeof(int), compare);
int option1 = nums[numsSize - 1] - nums[3];
int option2 = nums[numsSize - 2] - nums[2];
int option3 = nums[numsSize - 3] - nums[1];
int option4 = nums[numsSize - 4] - nums[0];
int min_diff = option1;
if (option2 < min_diff) min_diff = option2;
if (option3 < min_diff) min_diff = option3;
if (option4 < min_diff) min_diff = option4;
return min_diff;
}
// Example usage
int main() {
int nums1[] = {5, 3, 2, 4};
int nums2[] = {1, 5, 0, 10, 14};
int nums3[] = {3, 100, 20};
printf("%d\n", minDifference(nums1, 4)); // Output: 0
printf("%d\n", minDifference(nums2, 5)); // Output: 1
printf("%d\n", minDifference(nums3, 3)); // Output: 0
return 0;
}using System;
public class MinDifferenceSolution {
public int MinDifference(int[] nums) {
if (nums.Length <= 4) return 0;
Array.Sort(nums);
return Math.Min(
Math.Min(nums[nums.Length - 1] - nums[3], nums[nums.Length - 2] - nums[2]),
Math.Min(nums[nums.Length - 3] - nums[1], nums[nums.Length - 4] - nums[0])
);
}
public static void Main() {
int[] nums1 = {5, 3, 2, 4};
int[] nums2 = {1, 5, 0, 10, 14};
int[] nums3 = {3, 100, 20};
MinDifferenceSolution solution = new MinDifferenceSolution();
Console.WriteLine(solution.MinDifference(nums1)); // Output: 0
Console.WriteLine(solution.MinDifference(nums2)); // Output: 1
Console.WriteLine(solution.MinDifference(nums3)); // Output: 0
}
}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.
Approach 2: Default Approach
function minDifference(nums: number[]): number {
if (nums.length < 5) {
return 0;
}
nums.sort((a, b) => a - b);
let ans = Number.POSITIVE_INFINITY;
for (let i = 0; i < 4; i++) {
ans = Math.min(ans, nums.at(i - 4)! - nums[i]);
}
return ans;
}func minDifference(nums []int) int {
n := len(nums)
if n < 5 {
return 0
}
sort.Ints(nums)
ans := 1 << 60
for l := 0; l <= 3; l++ {
r := 3 - l
ans = min(ans, nums[n-1-r]-nums[l])
}
return ans
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Minimum Difference Between Largest and Smallest Value in Three Moves easy or hard?
The problem is rated Medium because the implementation is simple but the key insight is not immediately obvious. Recognizing that three moves only affect the extremes and reduce the problem to four scenarios is the main challenge.
Minimum Difference Between Largest and Smallest Value in Three Moves Python/Java solution
The typical Python or Java solution sorts the array and checks four ranges representing the removal of three extremes. The answer is the minimum difference among these ranges. The implementation is short, usually under 10 lines after sorting.
How to solve Minimum Difference Between Largest and Smallest Value in Three Moves in O(n)?
A strict O(n) approach without sorting is difficult because you must know the smallest and largest few elements simultaneously. However, you can approximate linear time using selection or heaps to track the smallest four and largest four values. After collecting these extremes, compute the same four candidate differences.
What is the best approach for Minimum Difference Between Largest and Smallest Value in Three Moves?
The optimal approach sorts the array and analyzes four possible windows after removing up to three extreme values. After sorting, compute the minimum of nums[n-4]-nums[0], nums[n-3]-nums[1], nums[n-2]-nums[2], and nums[n-1]-nums[3]. This greedy observation limits the solution space to four cases and runs in O(n log n) time due to sorting.
Is Minimum Difference Between Largest and Smallest Value in Three Moves asked at Google/Amazon/Meta?
Array and greedy optimization problems like this commonly appear in interviews at companies such as Amazon, Google, and Meta. The question tests whether you recognize that modifying elements effectively removes extreme values and reduces the problem to a few deterministic cases.
What data structure is used in Minimum Difference Between Largest and Smallest Value in Three Moves?
The primary data structure is a simple array combined with sorting. After sorting, the algorithm only compares values at the boundaries of four sliding windows. Some variations also use min-heaps and max-heaps to track the smallest and largest elements.
What is the time complexity of Minimum Difference Between Largest and Smallest Value in Three Moves?
The optimal solution runs in O(n log n) time because the array must be sorted. After sorting, evaluating the four candidate ranges takes constant time. Space complexity is O(1) if sorting is done in-place.