{x}
blog image

Minimum Difference Between Largest and Smallest Value in Three Moves

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
Explanation: 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 Explanation

This problem asks for the minimum difference between the largest and smallest values in an array after making at most three changes to the array elements. The core idea is to leverage the fact that we can change at most three elements. This means we can focus on eliminating the three largest or three smallest elements to minimize the difference.

Approach:

  1. Sort the Array: The most efficient way to approach this is to sort the array nums. This allows us to easily identify the smallest and largest elements.

  2. Greedy Approach: We consider all possible combinations of keeping a certain number of elements from the beginning and end of the sorted array. Since we have at most three moves, we can choose to eliminate elements from the beginning (smallest) or the end (largest) or a combination of both.

  3. Iterate Through Combinations: We iterate through four possible scenarios:

    • Keep nums[0] to nums[n-4] (eliminate 3 largest)
    • Keep nums[1] to nums[n-3] (eliminate 2 largest and 1 smallest)
    • Keep nums[2] to nums[n-2] (eliminate 1 largest and 2 smallest)
    • Keep nums[3] to nums[n-1] (eliminate 3 smallest)

  4. Calculate and Minimize: For each combination, we calculate the difference between the largest and smallest remaining elements ( nums[n - 1 - r] - nums[l] where l represents the starting index and r represents the number of elements removed from the end). We track the minimum difference found so far.

  5. Return Minimum Difference: After checking all combinations, the minimum difference is returned.

Time Complexity Analysis:

  • Sorting the array takes O(n log n) time, where n is the length of the array.
  • The loop iterates four times, performing constant-time operations within each iteration. Therefore, the loop contributes O(1) to the overall time complexity.

Thus, the dominant factor is the sorting step, making the overall time complexity O(n log n).

Space Complexity Analysis:

  • The space complexity is determined by the sorting algorithm used. In-place sorting algorithms (like merge sort or heapsort) have a space complexity of O(log n) due to the recursive calls. However, if an algorithm like timsort (often used in Python) is implemented, then it's O(n) due to temporary array usage. For simplicity and practicality, we can often consider the space complexity as O(log n) or O(n) depending on the specific implementation of the sorting algorithm used. If we don't count the space used by the input array, it's O(1).

Code (Python):

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 5:
            return 0
        nums.sort()
        ans = float('inf') # Initialize with infinity
        for l in range(4):  # Iterate through the four combinations
            r = 3 - l
            ans = min(ans, nums[n - 1 - r] - nums[l]) # Find the minimum difference
        return ans

The code in other languages follows the same logic, with only syntax variations. The core algorithm remains consistent across all languages.