[Java/C++/Python] Straight Forward
Intuition\nIf we can do 0 move, return max(A) - min(A)\nIf we can do 1 move, return min(the second max(A) - min(A),  the max(A) - second min(A))\nand so on.\n\n
# Intuition\nIf we can do 0 move, return max(A) - min(A)\nIf we can do 1 move, return min(the second max(A) - min(A),  the max(A) - second min(A))\nand so on.\n<br>\n\n# **Explanation**\nWe have 4 plans:\n1. kill 3 biggest elements\n2. kill 2 biggest elements + 1 smallest elements\n3. kill 1 biggest elements + 2 smallest elements\n3. kill 3 smallest elements\n<br>\n\nExample from @himanshusingh11:\n\n`A = [1,5,6,13,14,15,16,17]`\n`n = 8`\n\nCase 1: kill 3 biggest elements\n\nAll three biggest elements can be replaced with 14\n[1,5,6,13,14,`15,16,17`] -> [1,5,6,13,14,`14,14,14`] == can be written as `A[n-4] - A[0] == (14-1 = 13)`\n\nCase 2: kill 2 biggest elements + 1 smallest elements\n\n[`1`,5,6,13,14,15,`16,17`] -> [`5`,5,6,13,14,15,`15,15`] == can be written as `A[n-3] - A[1] == (15-5 = 10)`\n\nCase 3: kill 1 biggest elements + 2 smallest elements\n\n[`1,5`,6,13,14,15,16,`17`] -> [`6,6`,6,13,14,15,16,`16`] == can be written as `A[n-2] - A[2] == (16-6 = 10)`\n\nCase 4: kill 3 smallest elements\n\n[`1,5,6`,13,14,15,16,17] -> [`13,13,13`,13,14,15,16,17] == can be written as `A[n-1] - A[3] == (17-13 = 4)`\n\nAnswer is minimum of all these cases!\n<br>\n\n# Solution 1: Quick Sort\nI used quick sort to find out the biggest and smallest\nSo time and space are `O(quick sort)`\n<br>\n\n**C++**\n```cpp\n    int minDifference(vector<int>& A) {\n        int n = A.size();\n        if (n < 5) return 0;\n        sort(A.begin(), A.end());\n        return min({A[n - 1] - A[3], A[n - 2] - A[2], A[n - 3] - A[1], A[n - 4] - A[0]});\n    }\n```\n**Java**\n```java\n    public int minDifference(int[] A) {\n        int n = A.length, res = Integer.MAX_VALUE;\n        if (n < 5) return 0;\n        Arrays.sort(A);\n        for (int i = 0; i < 4; ++i) {\n            res = Math.min(res, A[n - 4 + i] - A[i]);\n        }\n        return res;\n    }\n```\n**Python:**\n```py\n    def minDifference(self, A):\n        A.sort()\n        return min(b - a for a, b in zip(A[:4], A[-4:]))\n```\n<br>\n\n# Solution 2: Partial Sorting\nChanged from @Sklert\nReference https://en.cppreference.com/w/cpp/algorithm/partial_sort\n\nTime `O(NlogK)`\nSpace `O(logK)`\n\n**C++**\n```cpp\n    int minDifference(vector<int>& A) {\n        int n = A.size();\n        if (n < 5)\n            return 0;\n        partial_sort(A.begin(), A.begin() + 4, A.end());\n        nth_element(A.begin() + 4, A.end() - 4, A.end());\n        sort(A.end() - 4, A.end());\n        return min({A[n - 1] - A[3], A[n - 2] - A[2], A[n - 3] - A[1], A[n - 4] - A[0]});\n    }\n```\n**Python**\n```py\n    def minDifference(self, A):\n        return min(a - b for a,b in zip(heapq.nlargest(4, A), heapq.nsmallest(4, A)[::-1]))\n```
[]