#1509

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Difference Between Largest and Smallest Value in Three Moves

Find the minimum difference between the largest and smallest values in an array after performing at most three moves.

Problem Statement

You are given an integer array nums. In one move, you can choose one element of nums and change it to any value. Your task is to return the minimum difference between the largest and smallest values of nums after performing at most three moves.

For example, in the array [5, 3, 2, 4], after performing three moves, you can change the elements to make the difference between the maximum and minimum values 0. The goal is to identify the optimal way to adjust the array elements to minimize the result.

Examples

Example 1

Input: nums = [5,3,2,4]

Output: 0

We can make at most 3 moves. In the first move, change 2 to 3. nums becomes [5,3,3,4]. In the second move, change 4 to 3. nums becomes [5,3,3,3]. In the third move, change 5 to 3. nums becomes [3,3,3,3]. After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

Example 2

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

Output: 1

We can make at most 3 moves. In the first move, change 5 to 0. nums becomes [1,0,0,10,14]. In the second move, change 10 to 0. nums becomes [1,0,0,0,14]. In the third move, change 14 to 1. nums becomes [1,0,0,0,1]. After performing 3 moves, the difference between the minimum and maximum is 1 - 0 = 1. It can be shown that there is no way to make the difference 0 in 3 moves.

Example 3

Input: nums = [3,100,20]

Output: 0

We can make at most 3 moves. In the first move, change 100 to 7. nums becomes [3,7,20]. In the second move, change 20 to 7. nums becomes [3,7,7]. In the third move, change 3 to 7. nums becomes [7,7,7]. After performing 3 moves, the difference between the minimum and maximum is 7 - 7 = 0.

Constraints

1 <= nums.length <= 105
-109 <= nums[i] <= 109

Solution Approach

Greedy Approach

To minimize the difference, we should focus on reducing the largest and smallest values. The best strategy is to remove the top three largest and bottom three smallest elements. By performing three moves on the most extreme values, the array will be adjusted for the minimum difference.

Sorting

Start by sorting the array. The smallest and largest values are on the edges. By considering combinations of removing three smallest and three largest elements, you can efficiently calculate the possible differences and determine the minimum possible difference.

Edge Case Considerations

For cases where the array has fewer than 4 elements, the problem simplifies since no move is needed. In these cases, return the difference between the maximum and minimum values directly.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity of the solution is O(n log n) due to sorting the array. Since we only consider the top three largest and smallest elements, the space complexity is O(1) as we only need constant extra space for comparisons.

What Interviewers Usually Probe

Look for a candidate who can efficiently implement the greedy approach.
The candidate should demonstrate an understanding of the impact of sorting on time complexity.
A good candidate will consider edge cases where fewer than four elements are present in the array.

Common Pitfalls or Variants

Common pitfalls

Failing to recognize that only three moves are allowed, and thus choosing more elements than necessary.
Not considering edge cases where the array is too small to perform any moves.
Overlooking the importance of sorting the array for efficient calculation of possible differences.

Follow-up variants

Allowing more than three moves and testing the impact on time complexity.
Implementing the solution without sorting, using a more efficient selection method.
Using a dynamic programming approach to test all combinations of three changes.

FAQ

What is the optimal way to minimize the difference in this problem?

The optimal way is to perform three moves on the extreme values (either the three smallest or three largest) to reduce the difference between the maximum and minimum values.

How do I handle edge cases in this problem?

For arrays with fewer than four elements, no move is needed, and the answer is simply the difference between the maximum and minimum values.

Why is sorting necessary for solving this problem?

Sorting allows easy access to the smallest and largest values in the array, making it simple to apply the greedy approach for minimizing the difference.

What happens if I allow more than three moves?

Allowing more than three moves would change the problem significantly, as it would require handling more than just the extreme elements, potentially leading to a higher time complexity.

How does the greedy strategy work in this problem?

The greedy strategy works by minimizing the maximum difference by removing the most extreme values in the array. By choosing the largest and smallest elements to adjust, you achieve the minimum difference with the least number of moves.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 5:
            return 0
        nums.sort()
        ans = inf
        for l in range(4):
            r = 3 - l
            ans = min(ans, nums[n - 1 - r] - nums[l])
        return ans

Continue Practicing

#1481 least number of unique integers after k removals #1465 maximum area of a piece of cake after horizontal and vertical cuts #1561 maximum number of coins you can get