O(n) time and O(1) space solution Python
The hardest part of this problem is recognizing the trick. The value you change the numbers in the array to need not be calculated, so changed values can be tre
The hardest part of this problem is recognizing the trick. The value you change the numbers in the array to need not be calculated, so changed values can be treated as though they are removed entirely. Also, notice that removing elements will never increase the spread of the numbers in an array, so we will use all 3 of our changes every time. The spread of numbers can be calculated as the largest value minus the smallest. If we remove the three smallest numbers, then we must subtract the 4th smallest from the largest number to get the spread. There are 4 other possible combinations of removals we must check (2 removed from front, 1 from back; 1 removed from front, 2 from back; 0 removed from front, 3 from back).\n\nIf we sort, then our solution is nlogn time. However, because we only really need to sort the first 4 and last 4 elements, we can just iterate over the loop in linear time, and eject elements from our min and max heaps when they\'re within the 4 largest or smallest elements encountered so far. Whether the array is 5 elements or 500, we iterate over it once, find the 4 smallest and largest, and put them in data structures that will never exceed length 4, so our time in O(n) and our space is constant.\n"""\n\n        if len(nums) < 5: #4 elements and 3 changes mean we can make all elements the same\n            return 0\n        s, l = [], []\n        mx, mn = [], []\n        h = heapq\n\t\t\n        for i in range(4):\n            h.heappush(s,-1*nums[i]) #max heap for 4 smallest values\n            h.heappush(l,nums[i]) #min heap for 4 largest values\n        \n        for i in nums[4:]:\n            if i > l[0]:\n                h.heappushpop(l,i)\n            if -1*i > s[0]:\n                h.heappushpop(s,-1*i)\n        for i in range(4):\n            mn.append(-1*h.heappop(s))\n            mx.append(h.heappop(l))\n        return min([mx[i]-mn[3-i] for i in range(4)])\n            \n"""
['Heap (Priority Queue)', 'Python']