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.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int minDifference(vector<int>& nums) {
8 if (nums.size() <= 4) return 0;
9 sort(nums.begin(), nums.end());
10 int n = nums.size();
11 return min({nums[n - 1] - nums[3], nums[n - 2] - nums[2], nums[n - 3] - nums[1], nums[n - 4] - nums[0]});
12}
13
14// Example usage
int main() {
vector<int> nums1 = {5, 3, 2, 4};
vector<int> nums2 = {1, 5, 0, 10, 14};
vector<int> nums3 = {3, 100, 20};
cout << minDifference(nums1) << endl; // Output: 0
cout << minDifference(nums2) << endl; // Output: 1
cout << minDifference(nums3) << endl; // Output: 0
return 0;
}The C++ solution utilizes the built-in sort function to sort the input vector. Then it calculates the minimal difference in a similar way as shown in the Python solution by analyzing four possible element arrangements.