nth_element & sort 4 smallest, biggest vs 2 heaps vs 1-liner||17ms Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nGreedy algorithm.\n\nSorting the whole array nums is easy, but the time complexity is r
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nGreedy algorithm.\n\nSorting the whole array nums is easy, but the time complexity is raised up to $O(n\\log n)$.\n\nTry nth_element to find the 4 smallest & 4 biggest ints, then sort.\n\nPython solution is 1-liner using sorting the whole nums.\n\n3rd approach uses maxheap & minheap to hold 4 smallest, biggest elements. This solution is linear & run in 26ms Beats 99.74%.\n\nAn optimized version is done as a variant for the 1st C++ code by adopting the suggestion of @Sergei avoiding of using extra space. That code has runtime 17ms & beats 100%.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. When n<=4,  just return 0\n2. Use `nth_element` to find the 4 smallest ints & store them in a 4 elemented array `small`; then sort\n3. Use `nth_element` to find the 4 biggest ints & store them in a 4 elemented array `big`; then sort\n4. Consider 4 scenarios min(big[i]-small[i] for i=0...3) which is the answer.\n5. Python 1 liner uses usual sort.\n6. 3rd approach uses maxheap `small` & minheap `big` to hold 4 smallest, biggest elements. This solution is linear & run in 26ms Beats 99.74%\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(8)=O(1)$$\n# Code C++ 28ms Beats 99.61%\n```\nclass Solution {\npublic:\n    static int minDifference(vector<int>& nums) {\n        const int n=nums.size();\n        if (n<=4) return 0;\n\n        //nth_element & sort find 4 smallest elements\n        nth_element(nums.begin(), nums.begin()+4, nums.end());\n        vector<int> small(nums.begin(), nums.begin()+4);\n        sort(small.begin(), small.end());\n\n        //nth_element & sort find 4 biggest elements\n        nth_element(nums.begin(), nums.begin()+4, nums.end(), greater<int>());\n        vector<int> big(nums.begin(), nums.begin()+4);\n        sort(big.begin(), big.end());\n\n        // difference by considering 4 scenarios\n        int min_diff=INT_MAX;\n        for (int i=0; i<=3; ++i) \n            min_diff = min(min_diff, big[i]-small[i]);\n        \n\n        return min_diff;\n    }\n};\n\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# Python 1-liner\n```\nclass Solution:\n    def minDifference(self, nums: List[int]) -> int:\n        return 0 if len(nums)<=4 else nums.sort() or min(nums[len(nums)-4+i]-nums[i] for i in range(4))\n        \n```\n# C++ using maxheap & min heap ||26ms Beats 99.74%\n```\nclass Solution {\npublic:\n    static int minDifference(vector<int>& nums) {\n        const int n=nums.size();\n        if (n<=4) return 0;\n        priority_queue<int> small;\n        priority_queue<int, vector<int>, greater<int>> big;\n        for (int x :nums){\n            if (small.size()>3){\n                if (x<small.top()){\n                    small.pop();\n                    small.push(x);\n                }\n            }\n            else small.push(x);\n            if (big.size()>3){\n                if (x>big.top()){\n                    big.pop();\n                    big.push(x);\n                }\n            }\n            else big.push(x);\n        }\n        \n        int Big[4];\n        for(int i=3; i>=0; i--){\n            Big[i]=big.top();\n            big.pop();\n        }\n\n        // difference by considering 4 scenarios\n        int min_diff=INT_MAX;\n        for (int i=0; i<=3; i++){ \n            int Small=small.top();\n            small.pop();\n            min_diff=min(min_diff, Big[i]-Small);\n        }\n\n        return min_diff;\n    }\n};\n\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# C++ using nth_element & sort 4 smallest, biggest ints||17ms beats 100%\n\nThanks to @Serger, no extra space for `small` & `big` in use. The use for nth_element & sort is also optimized.\n```\nclass Solution {\npublic:\n    static int minDifference(vector<int>& nums) {\n        const int n = nums.size();\n        if (n<=4) return 0;\n\n        //nth_element & sort find 4 smallest elements\n        nth_element(nums.begin(), nums.begin()+3, nums.end());\n        sort(nums.begin(), nums.begin()+3);\n\n        //nth_element & sort find 4 biggest elements\n        nth_element(nums.begin()+4, nums.end()-4, nums.end());\n        sort(nums.end()-3, nums.end());\n\n        // difference by considering 4 scenarios\n        int min_diff=INT_MAX;\n        for (int i=0; i<=3; ++i) \n            min_diff = min(min_diff, nums[n-4+i]-nums[i]);\n        \n\n        return min_diff;\n    }\n};\n\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\nSince the std::sort is used for sorting 3 elements twice, it can replaced by the following very easy function\n```\n    static void sort3(int& x, int& y, int& z){\n        if (y > z) swap(y, z); // Ensure y <= z\n        if (x > z) swap(x, z); // Ensure x <= z\n        if (x > y) swap(x, y); // Ensure x <= y\n    }\n```
['Array', 'Greedy', 'Sorting', 'Heap (Priority Queue)', 'C++', 'Python3']