Minimum Difference Between Largest and Smallest Value in Three Moves

Problem Description

Ah, the classic dilemma of life: how to minimize the difference between the largest and smallest values in a set of numbers. Imagine you’re at a party, and you have to choose the best snacks. You can only take three moves to rearrange the snack platter. Do you want to end up with a giant bowl of chips next to a sad, lonely carrot stick? Of course not! You want to make sure that the difference between the largest and smallest snack is as small as possible.

In this problem, you are given an array of integers, and you can make three moves to either increase the smallest values or decrease the largest values. Your goal? To find the minimum difference between the largest and smallest values after making those moves.

Code Solution


class Solution {
  public int minDifference(int[] nums) {
    final int n = nums.length;
    if (n < 5)
      return 0;

    int ans = Integer.MAX_VALUE;

    Arrays.sort(nums);

    // 1. Change nums[0..i) to nums[i].
    // 2. Change nums[n - 3 + i..n) to nums[n - 4 + i].
    for (int i = 0; i <= 3; ++i)
      ans = Math.min(ans, nums[n - 4 + i] - nums[i]);

    return ans;
  }
}

Approach

The approach here is quite straightforward. First, we sort the array. Then, we consider the four smallest and four largest numbers in the sorted array. By changing the smallest numbers to the next smallest and the largest numbers to the next largest, we can calculate the minimum difference. The loop runs four times, checking all possible combinations of changes to find the minimum difference.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n log n)
Space Complexity	O(1)

Real-World Example

Let’s say you’re at a buffet with a variety of dishes. You have three chances to swap out the least appealing dishes for something better. If you have a plate with a giant steak (largest value) and a sad little salad (smallest value), you want to make sure that after your swaps, you don’t end up with a plate that still has a huge difference between the best and worst items. This problem is all about making those swaps wisely!