1509. Minimum Difference Between Largest and Smallest Value in Three Moves

Problem

Question

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

Example 1:

Input: nums = [5,3,2,4] Output: 0 Explanation: 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 Explanation: 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

Constraints:

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

---

Solutions

1. Sort & Greedy Deletion

Time Complexity: $O(n\log n)$ | Space Complexity: $O(1)$

To solve this problem, we need to sort the array and find the best outcome. By outcome, we mean the minimum difference between the largest and smallest values after removing up to three outliers from either end. There are only four possible scenarios to consider:

• nums[-4] - nums[0] (delete 3 largest elements)
• nums[-3] - nums[1] (delete 2 largest and 1 smallest elements)
• nums[-2] - nums[2] (delete 1 largest and 2 smallest elements)
• nums[-1] - nums[3] (delete 3 smallest elements)

class Solution:
    def minDifference(self, nums: List[int]) -> int:
 
        if len(nums) <= 4:
            return 0
        
        nums.sort()
 
        min_diff = float('inf')
 
        for p1 in range(4):
            p2 = len(nums) - 4 + p1
            min_diff = min(min_diff, nums[p2] - nums[p1])
        
        return min_diff

Alternatively, we can return the minimum all 4 possible outcomes:

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0
        
        nums.sort()
        
        return min(nums[-4] - nums[0], nums[-3] - nums[1], nums[-2] - nums[2], nums[-1] - nums[3])
 

---

🏆 2. Partial Sorting

Time Complexity: $O(n)$ | Space Complexity: $O(1)$

We can improve the performance further by utilizing the heapq.nlargest and heapq.nsmallest functions. These functions allow us to efficiently find the top four largest and smallest elements in the array without sorting the entire list. Time complexity here is $O(n\log 4)$, which simplifies to $O(n)$.

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0
        
        largest = heapq.nlargest(4, nums)
        smallest = heapq.nsmallest(4, nums)
 
        min_diff = float('inf')
        for i in range(4):
            min_diff = min(min_diff, largest[i] - smallest[3 - i])
        
        return min_diff