Minimum Difference Between Largest and Smallest Value in Three Moves

Minimum Difference Between Largest and Smallest Value in Three Moves

1. What is this problem about?

In the Minimum Difference Between Largest and Smallest Value in Three Moves problem, you are given an array of integers. In one move, you can change any element of the array to any other value. You can perform at most three such moves. The goal is to minimize the difference between the largest and the smallest value in the array after the moves.

2. Why is this asked in interviews?

This "Medium" problem is frequently asked by Google and Microsoft because it requires a clever observation about which elements to change. The Minimum Difference Between Largest and Smallest Value in Three Moves interview question tests your ability to identify that to minimize the range, you should always target the extreme values (the largest or the smallest). It evaluates greedy thinking and case-based analysis.

3. Algorithmic pattern used

The algorithmic pattern is Greedy and Sorting. If we can change 3 elements, we should change them to values that already exist in our "target" range, effectively removing them from the calculation of the min/max. There are 4 scenarios to consider after sorting the array:

1. Change 3 smallest elements.
2. Change 2 smallest and 1 largest.
3. Change 1 smallest and 2 largest.
4. Change 3 largest elements. In each case, we calculate the new range of the remaining elements. This "Array, Sorting, Greedy interview pattern" allows us to find the minimum possible range by only checking these 4 boundaries.

4. Example explanation

Array: [1, 5, 0, 10, 14]. Sorted: [0, 1, 5, 10, 14].

• Remove 3 smallest (0, 1, 5): Range = $14 - 10 = 4$.
• Remove 2 smallest (0, 1) and 1 largest (14): Range = $10 - 5 = 5$.
• Remove 1 smallest (0) and 2 largest (10, 14): Range = $5 - 1 = 4$.
• Remove 3 largest (5, 10, 14): Range = $1 - 0 = 1$. The minimum difference is 1.

5. Common mistakes candidates make

A frequent mistake in the Minimum Difference Between Largest and Smallest Value in Three Moves coding problem is not considering all 4 combinations of removals. Some candidates only think about removing the 3 largest or 3 smallest. Another mistake is not handling arrays with 4 or fewer elements; in such cases, you can make all elements equal, resulting in a difference of 0.

6. Interview preparation tip

Practice identifying "boundary-heavy" problems. If an optimization only depends on the extreme values of a set, you usually only need to sort and check a few elements at the beginning and end. This "Extreme-value greedy interview pattern" is a common shortcut for problems that otherwise look like they might require complex searching.