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:

1. the three largest elements,
2. two largest and one smallest,
3. one largest and two smallest,
4. 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]:

1. Sort → [0,1,5,10,14], n=5
2. i=0: remove 0 smallest, 3 largest → remaining [0,1], diff=1−0=1
3. i=1: remove 1 smallest, 2 largest → remaining [1,5,10], diff=10−1=9
4. i=2: remove 2 smallest, 1 largest → remaining [5,10,14], diff=14−5=9
5. 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