One-pass solution with intuition | No sorting | Beats 99% | Python3
Intuition\nObserve that when making a move, there is no point in introducing a new number in the array - it is better to replace a number with something already
# Intuition\nObserve that when making a move, there is no point in introducing a new number in the array - it is better to replace a number with something already present elsewhere in the array, so as to not introduce a new max-min difference. This is equivalent to removing a number from the array.\n\nSo how do we remove 3 numbers from the array such that the new max-min difference is minimal? If we had to remove one number, clearly it would have to be the max or the min, else it makes no difference. We can extend this logic to considering a few largest and few smallest numbers and make a decision on which numbers to remove. These numbers can be found by simply iterating over the array. \n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(1)\n\n# Code\n```\nclass Solution:\n    def minDifference(self, nums: List[int]) -> int:\n        if len(nums) < 5:\n            return 0\n            \n        a, b, c, d, x, y, z, t = inf, inf, inf, inf, -inf, -inf, -inf, -inf\n        for num in nums:\n            if num < a:\n                d, c, b, a = c, b, a, num\n            elif num < b:\n                d, c, b = c, b, num\n            elif num < c:\n                d, c = c, num\n            elif num < d:\n                d = num\n\n            if num > t:\n                x, y, z, t = y, z, t, num\n            elif num > z:\n                x, y, z = y, z, num\n            elif num > y:\n                x, y = y, num\n            elif num > x:\n                x = num\n\n        return min(x - a,  y - b,  z - c, t - d)\n```
['Array', 'Greedy', 'Python3']