[C++] Try 4 Possible Choices After Sorting
Intuition\n Describe your first thoughts on how to solve this problem. \n- There are only 4 possible choices after sorting the integer array\n\n# Approach\n Des
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- There are only 4 possible choices after sorting the integer array\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Handle the base case\n  - when `nums.size() <= 4`, we can make all the elements to the same value in the array\n- Sort the integer array\n- Try 4 possible choices\n\n# Complexity\n- Time complexity: $$O(n\\log n)$$ for sorting\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(\\log n)$$ for sorting\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int minDifference(vector<int>& nums) {\n        // base case: we can make all the elements to the same value in the array\n        int n = nums.size();\n        if (n <= 4) return 0;\n\n        // sort the integer array\n        sort(nums.begin(), nums.end());\n\n        // there are 4 possible choices\n        return min({\n            nums[n - 1] - nums[3],      // discard 0 biggest and 3 smallest\n            nums[n - 2] - nums[2],      // discard 1 biggest and 2 smallest\n            nums[n - 3] - nums[1],      // discard 2 biggest and 1 smallest\n            nums[n - 4] - nums[0],      // discard 3 biggest and 0 smallest\n        });\n    }\n};\n```\n\n# Future Work\n- Use 2 priority queues (min. and max. heap) to record the 4 biggest and 4 smallest integers\n- The Time/Space complexity can be improved to $$O(n)$$/$$O(1)$$
['Greedy', 'Sorting', 'C++']