Simple O(N) | C++ | Partial Sort | Detailed explaination
We need to minimize the amplitude range (max_ele - min_ele) by changing at most 3 elements. \n\nIn order to do this, first we can sort the elements and then eit
We need to minimize the amplitude range (max_ele - min_ele) by changing at most 3 elements. \n\nIn order to do this, first we can **sort** the elements and then either\n**1. Kill last 3 elements\n2. Kill last 2 elements and first 1 element\n3. Kill last 1 element and first 2 element\n4. Kill first 3 elements**\nHere, killing would mean either changing it to new max_ele or new min_ele\n\nexample: \nnums: [1, 3, 5, 7, 8, 9, 10, 12, 13]\n1. Kill last 3 elements\n\ti.e. change last three elements to either 1 or 9 so whether we update it or forget about them at all won\'t matter. All we need is new_max_ele and new_min_ele\n\tnums: [1, 3, 5, 7, 8, 9, **9**, **9**, **9**]\n\tdiff = 9 - 1 = 8\n\t\n2. Kill last 2 elements and first 1 element\n\tnums: [**3**, 3, 5, 7, 8, 9, 10, **10**,**10**]\n\tdiff = 10 - 3 = 7\n\t\n3. Kill last 1 element and first 2 element\n\tnums: [**5**, **5**, 5, 7, 8, 9, 10, 12, **12**]\n\tdiff = 12 - 5 = 7\n\t\n4. Kill first 3 elements\n\tnums: [**7**, **7**, **7**, 7, 8, 9, 10, 12, 13]\n\tdiff = 13 - 7 = 6\nThus, min_diff = min(8, 7, 7, 6) = 6\n\nSorting will require **O(N logN)** time.\nBut wait!! Can we do better? Do we need to sort the whole array? (Observe: Does number 8 have any role in the above example?)\nNo, right? We only need to **sort the first 4 elements and the last 4 elements** and it would always lead to an optimal answer. \n\nIn C++, we can do this using [Partial Sorting](http://en.wikipedia.org/wiki/Partial_sorting).\nTime Complexity of Partial Sort: **O(N logK)** where\nN = total number of elements  \nK = number of elements from start to middle. \nHence, this works best when K <<<< N as compared to normal sort function. \nIn this problem, K = 4 and N can be as high as 10^5. (1 <= N <= 10^5)\n\nCode: \n```\nint minDifference(vector<int>& nums) {\n\tint n = nums.size();\n\t// for 1 <= n <= 4 we can always change all the numbers to equal numbers\n\tif(n < 5)\n\t\treturn 0;\n\t\n\t// first 4 elements\n\tpartial_sort(nums.begin(), nums.begin() + 4, nums.end());\n\t// last 4 elements\n    partial_sort(nums.rbegin(), nums.rbegin() + 4, nums.rend(), greater<int>());\n\t\n\tint min_diff = INT_MAX;\n\tfor(int i = 0, j = n - 4; i < 4; ++i, ++j)\n\t\tmin_diff = min(min_diff, nums[j] - nums[i]);\n        \n\treturn min_diff;\n}\n```\n\nTime Complexity: O(N * log(4) * 2) = **O(N)** \n\nHope this helps!! :D
['C', 'C++']