[Python] O(n) time O(1) space - Two heaps solution
Explanation:\n            First, handle the case for n<=4 is easy as it means the diff will be 0 always. so let\'s assume n >= 5.\n            Basically the max
Explanation:\n            First, handle the case for n<=4 is easy as it means the diff will be 0 always. so let\'s assume n >= 5.\n            Basically the max diff is determined by the diff between the biggest and smallest element.\n            Our options to remove elements are only to remove 3 elements between the combined list of first 3 and last 3.\n            Why remove? because removing is the same as changing value to some median value (easy to prove).\n            Look at the sorted array:\n            a0, a1, ...., a_(n-1)\n\n            And actually we have less options than previously stated. only 4 options:\n            - remove 0 from left and 3 from right\n            - remove 1 from left and 2 from right\n            - remove 2 from left and 1 from right\n            - remove 3 from left and 0 from right\n\n            My code checks exactly these 4 options.\n\n            All I need for these options calculations is the first and last 4 members of the sorted array.\n            I get them with min heap and max heap (implemented by negative min heap in my python code) with size at most 4.\n\n            Time: O(n)\n            Space: O(1)\n\nCode:\n\n```\nfrom heapq import *\nfrom typing import *\n\nclass Solution:\n    def minDifference(self, A: List[int]) -> int:\n        if len(A) <= 4: return 0\n\n        largestH, smallestH = [], []\n        for a in A:\n            heappush(largestH, a)\n            heappush(smallestH, -1 * a)\n            for H in [largestH, smallestH]:\n                if len(H) > 4:\n                    heappop(H)\n\n        smallest = sorted([-1 * h for h in smallestH])\n        largest = sorted(largestH, reverse=True)\n        res = float(\'inf\')\n        for i in range(3, -1, -1):\n            res = min(res, largest[i] - smallest[3 - i])\n        return res\n\n```
[]