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

class Solution {
public:
    int minDifference(vector<int>& nums)
    {
        int n = nums.size();
        if (n <= 4) return 0;

        int minDiff = INT_MAX;

        sort(nums.begin(), nums.end());

        int left = 0, right = n - 4;
        while (right < n)
        {
            minDiff = min(minDiff, nums[right] - nums[left]);
            ++left; ++right;
        }

        return minDiff;
    }
};

• T: $O(n \cdot \log n)$
• S: $O(n)$