Minimum Difference Between Largest and Smallest Value in Three Moves

medium greedy sorting array

Problem

You are given an integer array nums. In one move you may pick any element and change it to any value. After at most three moves, return the minimum possible difference between the largest and smallest value in the array.

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

Output1

Sorted: [0,1,5,10,14]. Three moves can erase any three elements; the best is to drop 5, 10, 14, leaving the gap 1 − 0 = 1.

Inputnums = [5,3,2,4]

Output0

With four or fewer elements, three moves can make every value equal, so the difference is 0.

nums (comma-separated)

def min_difference(nums):
    n = len(nums)
    if n <= 4:
        return 0
    nums.sort()
    best = float('inf')
    for i in range(4):
        hi = nums[n - 1 - (3 - i)]
        lo = nums[i]
        best = min(best, hi - lo)
    return best

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

int minDifference(int[] nums) {
    int n = nums.length;
    if (n <= 4) return 0;
    Arrays.sort(nums);
    int best = Integer.MAX_VALUE;
    for (int i = 0; i < 4; i++) {
        int hi = nums[n - 1 - (3 - i)];
        int lo = nums[i];
        best = Math.min(best, hi - lo);
    }
    return best;
}

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

Explanation

Each move replaces one element with anything we like. The only values that ever matter for the final spread are the current smallest and largest, so a smart move always rewrites one of the four extreme elements (the three smallest or three largest) into the middle of what remains.

That observation makes the problem tiny once the array is sorted. With three moves we get to erase exactly three elements from the two ends combined. We can drop i from the small end and 3 − i from the large end, for i = 0, 1, 2, 3 — only four choices.

For choice i the surviving range runs from index i up to index n − 1 − (3 − i), so the leftover difference is nums[n - 1 - (3 - i)] - nums[i]. We compute all four and keep the minimum.

If the array has four or fewer elements, three moves can flatten everything to one value, so the answer is simply 0 and we return early.

Sorting dominates the cost at O(n log n); the four candidate evaluations are constant work. Example: [1,5,0,10,14] sorts to [0,1,5,10,14], and dropping the three largest leaves 1 − 0 = 1, the best of the four windows.

Time: O(n log n) Space: O(1)