1509. Minimum Difference Between Largest and Smallest Value in Three Moves - Detailed Explanation

Problem Statement

Given an integer array nums, you may perform at most three moves. In each move, you can choose any element of nums and change it to any value. Return the minimum possible difference between the largest and smallest value in nums after at most three moves.

Examples

Input: nums = [5,3,2,4]
Output: 0
Explanation: We can change 5→3, 4→3, and 2→3, then all elements are 3.

Input: nums = [1,5,0,10,14]
Output: 1
Explanation: One optimal way is change 14→1, 10→1, 5→1. Array becomes [1,1,0,1,1], difference = 1.

Input: nums = [6,6,0,1,1,4,6]
Output: 2
Explanation: Change three of the 6’s to 1 → remaining values {0,1,1,4}, difference = 4–0 = 4; better is change {0,1,1} up to 4, leaving {4,4,4,6}, diff = 6–4 = 2.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁹
You may make at most 3 moves.

Approach – Sort and Remove Extremes

Explanation

After at most three moves, you can “fix” any three elements to lie within the target range. Equivalently, imagine deleting any three elements from the sorted array—the difference between the new max and min of the remaining elements is the answer. Sort nums and consider four scenarios, removing:

the three largest elements,
two largest and one smallest,
one largest and two smallest,
the three smallest elements.

Formally, let a be the sorted array and n its length. For i from 0 to 3, remove the first i elements and the last 3−i elements; compute

diff_i = a[n−4+i] − a[i]

The result is the minimum of these four differences.

Step‑by‑step Walkthrough

For [1,5,0,10,14]:

Sort → [0,1,5,10,14], n=5
i=0: remove 0 smallest, 3 largest → remaining [0,1], diff=1−0=1
i=1: remove 1 smallest, 2 largest → remaining [1,5,10], diff=10−1=9
i=2: remove 2 smallest, 1 largest → remaining [5,10,14], diff=14−5=9
i=3: remove 3 smallest, 0 largest → remaining [10,14], diff=14−10=4
Minimum = 1

Visual Example

Sorted: [0, 1, 5, 10, 14]
i=0 → keep     [0,1]       diff=1
i=1 → keep    [1,5,10]     diff=9
i=2 → keep   [5,10,14]     diff=9
i=3 → keep      [10,14]    diff=4
Answer = 1

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

Complexity Analysis

Time: O(n log n) to sort, plus O(1) for the four-difference checks → overall O(n log n).
Space: O(1) extra (beyond input), or O(log n) if the sorting algorithm uses recursion.

Common Mistakes

Forgetting the early return when n ≤ 4 → you can make all elements equal, so answer is 0.
Mis‑indexing when computing a[n−4+i] or a[i].
Sorting in descending order or forgetting to sort at all.

Edge Cases

Very small arrays (length 1–4)
All elements identical → result 0
Arrays already nearly uniform except one or two outliers
Very large values near the integer limits (but subtraction stays in 64-bit)

Alternative Variations

Generalized k moves: remove k extremes → window of size n−k → slide over sorted array and pick minimal window span.
At most k moves with cost constraints on each change.
Minimize range of a sliding window of fixed length in the array.