LeetCode 1509 - Minimum Difference Between Largest and Smallest Value in Three Moves

The problem gives us an integer array nums, and we are allowed to perform at most three moves. In each move, we may sele

leetcodemediumarraygreedysorting

LeetCode Problem 1509

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem gives us an integer array nums, and we are allowed to perform at most three moves. In each move, we may select any element and change it to any value we want. After making up to three modifications, we must minimize the difference between the largest and smallest values remaining in the array.

In other words, we want the final array to have its values as tightly grouped as possible. The output is the minimum possible value of:

$$\text{max(nums)} - \text{min(nums)}$$

after changing at most three elements.

The input array can contain up to $10^5$ elements, so the solution must be efficient. A quadratic or exponential solution would be far too slow for the constraints. The values themselves may range from $-10^9$ to $10^9$, but the magnitude of the numbers does not matter much because we only compare and sort them.

One important observation is that changing an element to any value effectively allows us to "remove" problematic extreme values. Since we can perform at most three moves, we can eliminate up to three outliers from either end of the sorted array.

Several edge cases are important:

  • If the array has length less than or equal to 4, we can modify every element except possibly one, making all numbers equal. The answer is therefore always 0.
  • Arrays with duplicate values must still be handled correctly after sorting.
  • Negative values do not introduce special logic because ordering still works normally.
  • Large arrays require an $O(n \log n)$ or better solution.

Approaches

Brute Force Approach

A brute force solution would attempt every possible combination of up to three elements to modify, and then determine the best values to assign to those elements.

Conceptually, this works because every possible valid configuration is explored. However, this becomes computationally infeasible very quickly.

If the array has size $n$, choosing three elements already requires:

$$O(n^3)$$

combinations. For each combination, we would also need to recompute the resulting minimum and maximum values, adding additional overhead.

With $n = 10^5$, such an approach is impossible to run within time limits.

Key Insight for the Optimal Solution

The crucial observation is that only the smallest and largest values matter.

Suppose the array is sorted:

$$a_0 \le a_1 \le a_2 \le \dots \le a_{n-1}$$

Since we can modify at most three elements, the optimal strategy must remove elements from the extremes.

There are only four possible ways to spend the three moves:

  1. Remove the three largest elements
  2. Remove two largest and one smallest
  3. Remove one largest and two smallest
  4. Remove the three smallest elements

After sorting, each scenario corresponds to keeping a continuous middle segment.

The resulting differences are:

$$a_{n-4} - a_0$$

$$a_{n-3} - a_1$$

$$a_{n-2} - a_2$$

$$a_{n-1} - a_3$$

The minimum among these four possibilities is the answer.

Because we only sort once and evaluate four cases, the algorithm is efficient.

Approach Time Complexity Space Complexity Notes
Brute Force $O(n^3)$ or worse $O(1)$ Tries combinations of elements to modify
Optimal $O(n \log n)$ $O(1)$ or $O(\log n)$ depending on sort Sort once, evaluate four possibilities

Algorithm Walkthrough

  1. First, check whether the array length is less than or equal to 4.

If there are at most four elements, we can change enough elements to make the entire array equal. Therefore, the minimum difference is 0. 2. Sort the array in nondecreasing order.

Sorting allows us to reason about smallest and largest values directly. Once sorted, the only values that matter are near the boundaries. 3. Initialize the answer with a very large number.

We will compute the minimum difference among four possible scenarios. 4. Evaluate removing the three largest elements.

This means the remaining effective range is from nums[0] to nums[n-4].

Difference:

$$nums[n-4] - nums[0]$$ 5. Evaluate removing two largest elements and one smallest element.

Remaining range:

$$nums[1] \text{ to } nums[n-3]$$

Difference:

$$nums[n-3] - nums[1]$$ 6. Evaluate removing one largest element and two smallest elements.

Remaining range:

$$nums[2] \text{ to } nums[n-2]$$

Difference:

$$nums[n-2] - nums[2]$$ 7. Evaluate removing the three smallest elements.

Remaining range:

$$nums[3] \text{ to } nums[n-1]$$

Difference:

$$nums[n-1] - nums[3]$$ 8. Return the minimum among all four differences.

Why it works

After sorting, any optimal solution must eliminate elements only from the ends of the array. Changing an interior element cannot reduce the global minimum or maximum as effectively as changing an extreme value.

Since we have exactly three moves available, the only possibilities are distributing those moves between the smallest and largest elements. The four scenarios exhaust all valid distributions of three removals across the two ends, guaranteeing that the minimum computed difference is optimal.

Python Solution

from typing import List

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)

        if n <= 4:
            return 0

        nums.sort()

        answer = float("inf")

        for left_removed in range(4):
            right_removed = 3 - left_removed

            current_difference = (
                nums[n - 1 - right_removed] -
                nums[left_removed]
            )

            answer = min(answer, current_difference)

        return answer

The implementation begins by checking whether the array contains four or fewer elements. In that situation, we can always make every value equal within three moves, so the result is immediately 0.

Next, the array is sorted. Sorting is the key step because it allows the algorithm to focus only on boundary values rather than arbitrary positions.

The loop iterates through the four possible distributions of removals. The variable left_removed represents how many smallest elements are effectively discarded, while right_removed represents how many largest elements are discarded.

For each configuration, we compute the difference between the new effective maximum and minimum values. The smallest such difference becomes the final answer.

The implementation is concise because the mathematical observation reduces the problem to evaluating only four cases.

Go Solution

package main

import (
	"math"
	"sort"
)

func minDifference(nums []int) int {
	n := len(nums)

	if n <= 4 {
		return 0
	}

	sort.Ints(nums)

	answer := math.MaxInt32

	for leftRemoved := 0; leftRemoved < 4; leftRemoved++ {
		rightRemoved := 3 - leftRemoved

		currentDifference := nums[n-1-rightRemoved] - nums[leftRemoved]

		if currentDifference < answer {
			answer = currentDifference
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python solution. The main difference is that Go requires explicit imports for sorting and integer constants.

sort.Ints(nums) sorts the slice in place. The loop structure mirrors the Python version exactly.

Go slices are reference types, so sorting modifies the original slice directly. Integer overflow is not an issue here because the problem constraints fit safely within Go's int type on modern systems.

Worked Examples

Example 1

Input:

nums = [5,3,2,4]

Since the array length is 4, we can modify all necessary elements to make every number equal.

Result:

0

Example 2

Input:

nums = [1,5,0,10,14]

After sorting:

[0,1,5,10,14]
Left Removed Right Removed Remaining Range Difference
0 3 0 to 1 1
1 2 1 to 5 4
2 1 5 to 10 5
3 0 10 to 14 4

Minimum difference:

1

Example 3

Input:

nums = [3,100,20]

Array length is 3, so we can make all values equal within three moves.

Result:

0

Complexity Analysis

Measure Complexity Explanation
Time $O(n \log n)$ Sorting dominates the runtime
Space $O(1)$ or $O(\log n)$ Depends on sorting implementation

The algorithm sorts the array once, which requires $O(n \log n)$ time. After sorting, only four constant-time computations are performed.

The extra space usage is minimal. Aside from the sorting implementation's internal stack space, the algorithm uses only a few variables.

Test Cases

from typing import List

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)

        if n <= 4:
            return 0

        nums.sort()

        answer = float("inf")

        for left_removed in range(4):
            right_removed = 3 - left_removed

            current_difference = (
                nums[n - 1 - right_removed] -
                nums[left_removed]
            )

            answer = min(answer, current_difference)

        return answer

solution = Solution()

assert solution.minDifference([5, 3, 2, 4]) == 0  # Example 1
assert solution.minDifference([1, 5, 0, 10, 14]) == 1  # Example 2
assert solution.minDifference([3, 100, 20]) == 0  # Example 3

assert solution.minDifference([1]) == 0  # Single element
assert solution.minDifference([1, 2]) == 0  # Two elements
assert solution.minDifference([1, 2, 3]) == 0  # Three elements
assert solution.minDifference([1, 2, 3, 4]) == 0  # Four elements

assert solution.minDifference([1, 5, 6, 14, 15]) == 1  # Remove extremes
assert solution.minDifference([1, 1, 1, 1, 1]) == 0  # All equal
assert solution.minDifference([-10, -5, 0, 5, 10]) == 5  # Negative values
assert solution.minDifference([100, 200, 300, 400, 500, 600]) == 200  # Larger sorted input
assert solution.minDifference([6, 6, 0, 1, 1, 4, 6]) == 2  # Duplicates
assert solution.minDifference([82, 81, 95, 75, 20]) == 1  # Mixed values
Test Why
[5,3,2,4] Validates small array optimization
[1,5,0,10,14] Standard mixed-value example
[3,100,20] Array size less than 4
[1] Single element edge case
[1,2] Two-element edge case
[1,2,3] Three-element edge case
[1,2,3,4] Four-element edge case
[1,5,6,14,15] Requires careful removal selection
[1,1,1,1,1] Already equal values
[-10,-5,0,5,10] Negative numbers
[100,200,300,400,500,600] Larger ordered array
[6,6,0,1,1,4,6] Duplicate values
[82,81,95,75,20] Unsorted mixed input

Edge Cases

One important edge case occurs when the array length is less than or equal to four. Since we may perform up to three moves, we can always change enough elements to make every value identical. A naive implementation that blindly accesses indices like nums[n-4] would crash for small arrays. The implementation avoids this by returning 0 immediately for arrays of size four or smaller.

Another critical edge case involves duplicate values. Arrays such as [1,1,1,1,1] already have a minimum difference of zero. Some incorrect solutions may still attempt unnecessary modifications or mis-handle equal elements after sorting. The current implementation works naturally because the computed differences remain zero.

Negative values are also important. Since the problem allows values as small as $-10^9$, the algorithm must not assume positivity. Sorting correctly orders negative numbers, and subtraction still produces the proper range difference. For example, [-10,-5,0,5,10] is processed exactly the same way as positive-only arrays.

A final subtle case is when the optimal solution removes elements from both ends rather than just one side. For example, in [1,5,0,10,14], the best answer comes from removing one smallest and two largest values. Solutions that only consider removing the three largest or three smallest values would fail. Evaluating all four distributions guarantees correctness.