Minimum Difference Between Largest and Smallest Value in Three Moves

Given an integer array nums, you can change at most 3 elements to any value you want. Return the minimum difference between the largest and smallest values in the array after making at most 3 changes. This is LeetCode 1509: Minimum Difference Between Largest and Smallest Value in Three Moves.

For example, given nums = [20, 1, 14, 6, 13, 5], you can change at most 3 elements. The optimal strategy is to change the three largest values (20, 14, 13) so the remaining spread is minimized. After sorting and checking all options, the answer is 5.

Why this problem matters

This problem teaches you to think about what "change to any value" really means. When you can set an element to anything, you are effectively removing it from consideration. That reframing turns a vague optimization into a concrete sliding window question on a sorted array.

It also reinforces the pattern of reducing a problem's complexity by sorting first. Many greedy and array problems become simple once you sort and then examine a small number of candidates. Here, sorting reduces the problem to just four comparisons.

The key insight

If you can change at most 3 elements, you are keeping at least n - 3 elements unchanged. The minimum difference equals the smallest range that covers any n - 3 consecutive elements in the sorted array.

After sorting, the n - 3 consecutive elements you keep must form a contiguous window. There are exactly 4 ways to remove 3 elements from the ends of a sorted array:

• Remove 0 from the left and 3 from the right
• Remove 1 from the left and 2 from the right
• Remove 2 from the left and 1 from the right
• Remove 3 from the left and 0 from the right

For each window, the difference is nums[n - 1 - right] - nums[left]. You take the minimum across all four.

The solution

def min_difference(nums):
    n = len(nums)
    if n <= 4:
        return 0

    nums.sort()

    result = float("inf")
    for left in range(4):
        right = 3 - left
        diff = nums[n - 1 - right] - nums[left]
        result = min(result, diff)

    return result

Here is what each part does:

1. Base case: if the array has 4 or fewer elements, you can change all of them. The difference is 0.
2. Sort: sorting takes O(n log n) and lets you examine windows by index.
3. Four windows: the loop iterates over the four possible splits. left is the number of elements removed from the front, right = 3 - left is the number removed from the back. The difference for each window is nums[n - 1 - right] - nums[left].
4. Take the minimum: result tracks the smallest difference seen across all four windows.

Visual walkthrough

Let's walk through the example nums = [20, 1, 14, 6, 13, 5] step by step.

The key observation is that once the array is sorted, you only need to compare four pairs of values. No nested loops, no dynamic programming. Just sort and scan.

Complexity analysis

The four-window scan itself is O(1) since it always checks exactly 4 candidates. The bottleneck is the sort.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Sort-then-scan

Many problems follow this template: sort the input, then scan a small number of candidates to find the answer. Sorting transforms unstructured data into something you can reason about positionally. Once sorted, you know the smallest and largest values are at the ends, and any contiguous subarray of size k contains the k closest values.

This same pattern appears in problems like Three Sum, Merge Intervals, and Meeting Rooms. The sort does the heavy lifting, and the scan is often O(n) or even O(1).

2. Greedy endpoint trimming

The idea of removing elements from the ends of a sorted array to minimize a metric is a greedy pattern. You do not need to try all possible subsets of 3 elements. Because the array is sorted, the elements that contribute most to the spread are always at the ends. This reduces an exponential search to a constant number of checks.

You will see this pattern in problems where you need to minimize the range, maximize a window, or find the tightest bound on sorted data.

Edge cases

Before submitting, make sure your solution handles these:

• Array with 4 or fewer elements: you can change everything, so the answer is always 0.
• All elements are equal: nums = [3, 3, 3, 3, 3]. After sorting, every window has diff = 0. Correct.
• Already sorted input: the algorithm does not assume unsorted input, but it works the same either way.
• Large values: elements can be up to 10^9. Use appropriate integer types if your language requires it (Python handles this natively).
• Array of exactly 5 elements: only one element is kept "as is" in terms of window size. For nums = [1, 2, 3, 100, 200], the windows give diffs of [3 - 1, 100 - 2, 200 - 3, 200 - 100] = [2, 98, 197, 100]. The answer is 2.
• Negative numbers: nums = [-10, -5, 0, 5, 10]. Sorting still works. Window diffs: [5 - (-10), 10 - (-5), ...] . The algorithm handles negatives without any special logic.

From understanding to recall

You have read through the solution and it makes sense. Sort, check four windows, take the minimum. Clean and short. But can you write it from scratch in an interview without peeking?

The details matter: remembering that there are exactly 4 windows, that right = 3 - left, and that the index for the right boundary is n - 1 - right. These are small but critical, and they are easy to mix up under pressure.

Spaced repetition closes that gap. You practice writing the sort-and-scan loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "minimize range by removing k elements" and the four-window approach flows out naturally.

The sort-then-scan pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Sort Colors - Another sorting problem where understanding the structure of the data eliminates brute force
• Merge Intervals - Sort-then-scan applied to interval merging
• Largest Number At Least Twice of Others - Reasoning about array extremes after identifying the maximum

CodeBricks breaks the minimum difference problem into its sort-then-scan and greedy trimming building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a sorting or greedy question shows up in your interview, you do not think about it. You just write it.