1509. 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 by any value.

Return the minimum difference between the largest and smallest value of nums after performing at most three moves.

class Solution {
    int heapSolution(vector<int>& nums) { //o(nlog5)
        priority_queue<int, vector<int>, greater<int>> minHeap; //has max value
        priority_queue<int> maxHeap; //has min value
        
        for(int i = 0; i < nums.size(); i++) {
            minHeap.push(nums[i]);
            maxHeap.push(nums[i]);
            if(maxHeap.size() >= 5) maxHeap.pop();
            if(minHeap.size() >= 5) minHeap.pop();
        }
        vector<int> n;
        while(!minHeap.empty()) {
            n.push_back(minHeap.top());
            minHeap.pop();
        }
        while(!maxHeap.empty()) {
            n.push_back(maxHeap.top());
            maxHeap.pop();
        }
        sort(n.begin(), n.end());
        return slidingWindow(n);
    }
    
    int slidingWindow(vector<int>& nums) {
        int res = INT_MAX;
        for(int l = 0, r = nums.size() - 4; l < 4; l++,r++) {
            res = min(res, nums[r] - nums[l]);
        }
        return res;
    }
public:
    int minDifference(vector<int>& nums) {
        if(nums.size() <= 4) return 0; //we can change all values;
        if(nums.size() >= 8) return heapSolution(nums);
        sort(nums.begin(), nums.end()); //o(nlogn)
        return slidingWindow(nums);
    }
};