[Python3] 1-line O(N)
Algo\nHere, at most 8 numbers are relevant, i.e. the 4 smallest and the 4 largest. Suppose they are labeled as \n\nm1, m2, m3, m4, ... M4, M3, M2, M1 \n\nthen m
Algo\nHere, at most 8 numbers are relevant, i.e. the 4 smallest and the 4 largest. Suppose they are labeled as \n\n`m1, m2, m3, m4, ... M4, M3, M2, M1` \n\nthen `min(M4-m1, M3-m2, M2-m3, M1-m4)` gives the solution. It is linear `O(N)` to find `m1-m4` and `M1-M4` like below. \n\n`O(N)` time & `O(1)` space leveraging on the `heapq` module \n\n```\nclass Solution:\n    def minDifference(self, nums: List[int]) -> int:\n        return min(x-y for x, y in zip(nlargest(4, nums), reversed(nsmallest(4, nums))))\n```\n\nA more readable version is below \n```\nclass Solution:\n    def minDifference(self, nums: List[int]) -> int:\n        small = nsmallest(4, nums)\n        large = nlargest(4, nums)\n        return min(x-y for x, y in zip(large, reversed(small)))\n```
['Python3']