Problem Description

You are given an integer array nums. You can make at most three moves. In each move, you can remove any element from the array (not necessarily consecutive or unique elements, but you cannot remove the same element more than once).

After performing at most three moves, return the minimum possible difference between the largest and smallest values in the resulting array.

• Each move removes one element, and you can remove up to three elements in total.
• You may choose to remove fewer than three elements if that yields a better result.
• The goal is to minimize max(nums) - min(nums) after up to three removals.
• It is guaranteed that the array has at least one element, and the answer always exists.

Thought Process

At first glance, one might think about trying all possible ways to remove up to three elements and then calculate the difference between the largest and smallest remaining values. However, the number of ways to remove three elements from a large array is enormous (combinatorial explosion), making brute-force impractical.

Instead, let's consider what actually changes the min and max of the array. Since we can remove up to three elements, the optimal strategy is to remove the largest elements (to decrease the max) or the smallest elements (to increase the min). The minimum possible difference will be achieved by removing some combination of the largest and smallest values.

Therefore, instead of checking every subset, we can focus on the four smallest and four largest numbers. For each possible way to allocate three removals between the smallest and largest elements, we can compute the difference and choose the minimum.

Solution Approach

• Step 1: Sort the array nums in non-decreasing order. This makes it easy to access the smallest and largest values.
• Step 2: Consider the four smallest and four largest numbers. Since we can remove up to three elements, there are four ways to split the removals:
  • Remove 0 smallest, 3 largest
  • Remove 1 smallest, 2 largest
  • Remove 2 smallest, 1 largest
  • Remove 3 smallest, 0 largest
• Step 3: For each of the four options, calculate the difference between the corresponding min and max:
  • After removing i smallest and 3 - i largest, the remaining array starts at index i and ends at index n - 1 - (3 - i).
  • Compute the difference: nums[n - 1 - (3 - i)] - nums[i]
• Step 4: Return the minimum difference found among the four cases.
• Edge Case: If the array has 4 or fewer elements, you can remove all but one, so the minimum difference is 0.

This approach is efficient and leverages sorting to reduce the problem to just four calculations.

Example Walkthrough

Let's consider the input nums = [5, 3, 2, 4].

• Sort: [2, 3, 4, 5]
• Since there are only 4 elements, we can remove 3, leaving just one number, so the minimum difference is 0.

Now, let's try a larger array: nums = [1, 5, 6, 14, 15]

• Sort: [1, 5, 6, 14, 15]
• Possible removals and differences:
  • Remove 0 smallest, 3 largest: remaining [1, 5], difference 5 - 1 = 4
  • Remove 1 smallest, 2 largest: remaining [5, 6], difference 6 - 5 = 1
  • Remove 2 smallest, 1 largest: remaining [6, 14], difference 14 - 6 = 8
  • Remove 3 smallest, 0 largest: remaining [14, 15], difference 15 - 14 = 1
• The minimum difference is 1.

Code Implementation

class Solution:
    def minDifference(self, nums):
        n = len(nums)
        if n <= 4:
            return 0
        nums.sort()
        return min(
            nums[n - 1 - i] - nums[i]
            for i in range(4)
        )
      

class Solution {
public:
    int minDifference(vector<int>& nums) {
        int n = nums.size();
        if (n <= 4) return 0;
        sort(nums.begin(), nums.end());
        int res = INT_MAX;
        for (int i = 0; i <= 3; ++i) {
            res = min(res, nums[n - 1 - i] - nums[i]);
        }
        return res;
    }
};
      

import java.util.Arrays;
class Solution {
    public int minDifference(int[] nums) {
        int n = nums.length;
        if (n <= 4) return 0;
        Arrays.sort(nums);
        int res = Integer.MAX_VALUE;
        for (int i = 0; i <= 3; ++i) {
            res = Math.min(res, nums[n - 1 - i] - nums[i]);
        }
        return res;
    }
}
      

var minDifference = function(nums) {
    const n = nums.length;
    if (n <= 4) return 0;
    nums.sort((a, b) => a - b);
    let res = Infinity;
    for (let i = 0; i <= 3; ++i) {
        res = Math.min(res, nums[n - 1 - i] - nums[i]);
    }
    return res;
};
      

Time and Space Complexity

• Brute-Force Approach: Would require checking all possible ways to remove up to three elements, which is O(n^3) (since there are C(n, 3) ways to remove three elements). This is not feasible for large n.
• Optimized Approach:
  • Sorting the array takes O(n \log n) time.
  • After sorting, we compute four differences in O(1) time.
  • Space complexity is O(1) extra (if sorting in-place), or O(n) if a new array is created.

Thus, the overall time complexity is O(n log n) and space complexity is O(1) (in-place).

Summary

The key insight is that the minimum difference after up to three removals is determined by removing the largest or smallest elements, not by considering all possible subsets. By sorting and considering only the four smallest and four largest numbers, we reduce the problem to four quick calculations. This elegant approach is both efficient and easy to implement, making it suitable for large input sizes.