Skip to main content
Talentd

Minimum Difference Between Largest and Smallest Value in Three Moves - Solution & Explanation

MediumArrayGreedySorting11 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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.

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.

Code

PythonCC++JavaC#JavaScript

Python

C

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) since the sorting is in-place.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Extremes SimulationO(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 TrackingO(n log k)O(k)Useful when only the smallest and largest few elements are required without fully sorting

Video Solution

Minimum Difference Between Largest and Smallest Value in Three Moves - Leetcode 1509 - Python • NeetCodeIO • 13,780 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Difference Between Largest and Smallest Value in Three Moves with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimize the Maximum Difference of Pairs