Python Solution | Explained | O(n) time, O(1) space complexity
Python Solution | Explained | O(n) time, O(1) space complexity\n\nThe current problem can be easily solved after observing the following:\n\n1. Only the largest
**Python Solution | Explained | O(n) time, O(1) space complexity**\n\nThe current problem can be easily solved after observing the following:\n\n1. Only the largest and smallest values found in the array affect the solution, since they cause the greatest differences. For example, if we imagine the sorted array [a, b, c, d, e, f, g, h, i, j, k], the optimal answer will be found after removing elements from [a,d] and/or [h,k]. Only the top-4 elements at each side are important. \n\n2. While sorting makes sense (under the previous context), we can find the top-4 highest and lowest elements of the array using an algorithm with O(n) time complexity (sorting is O(n log n) ). Different O(n) algorithms can be chosen. The code below uses heaps of size=4 to find the top-4 values at each side. This still has a time complexity of O(n), because O( n * log(4) ) = O(n).\n\n3. To avoid unnecesary calculations, we notice that it\'s always optimal to delete "x" elements from one side, and "3-x" elements from the other extreme. As a result, we can find the optimal answer with only 4 queries for each side ( x= [0,1,2,3] removals).\n\n4. Since our algorithm only stored small arrays up to size=4, we can conclude that our solution has O(1) space complexity.\n\n```\nimport heapq\nclass Solution:\n    def minDifference(self, A):\n        # 1) Trivial cases\n        if len(A)<=4:\n            return 0\n        #\n        # 2) Find: routine to find the top-4 highest or lowest elements (both cases are covered)\n        def find(high):\n            k    = 1 if high else -1\n            heap = [ k*x for x in A[:4] ]\n            heapq.heapify(heap)\n            for x in A[4:]:\n                heapq.heappushpop(heap,k*x)\n            return sorted([ k*x for x in heap ])\n        #\n        # 3) Fetch the top-4 elements at each extreme\n        big   = find(high=True)\n        small = find(high=False)\n        #\n        # 4) Find the optimal answer\n        return min([ (big[-4+i] - small[i]) for i in range(4) ])\n```\n\n**PS. Shorter Version**\nI recently learned about the existence of the functions "nlargest" and "nsmallest" in the "heapq" library, which simplify the code a lot. The time and space complexity are still O(n) and O(1) respectively. Cheers,\n\n```\n\nimport heapq\nclass Solution:\n    def minDifference(self, A):\n        # 1) Trivial case\n        if len(A)<=4:\n            return 0\n        #\n        # 2) Fetch the top-4 elements at each extreme\n        big   = heapq.nlargest(4,A)[::-1]\n        small = heapq.nsmallest(4,A)\n        #\n        # 4) Find the optimal answer\n        return min([ (big[-4+i] - small[i]) for i in range(4) ])\n```\n**Appendix: Sorting Method (Not Recommended)**\n\nWhile this algorithm isn\'t recommended due to its higher time complexity O( n log n), LeetCode might rate it as equally fast since most test cases involve small arrays, where the log(n) difference is negligible. \n\n```\nclass Solution:\n    def minDifference(self, A):\n        if len(A)<=4:\n            return 0\n        #\n        A.sort()\n        return min([ (A[-4+i] - A[i]) for i in range(4) ])\n```
['Python', 'Python3']