Sponsored
The idea is to sort the array and find the minimal difference after removing at most three elements from either side. By sorting the array, you can easily identify the largest and smallest values that might stay in the array. After sorting, the array becomes an ordered sequence, allowing you to attempt minimizing differences by changing elements from the edges.
This approach essentially checks the possible combinations of keeping n - 3 elements and removing the smallest, or the largest, or a mix of both.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) since the sorting is in-place.
1def minDifference(nums):
2 if len(nums) <= 4:
3 return 0
4 nums.sort()
5 return
This Python solution first checks if the array length is less than or equal to 4, in which case the result is 0 because we can change all elements in at most 3 moves. It then sorts the array and calculates the minimal difference by considering four potential scenarios: removing either the largest three, the smallest three, or combinations thereof.