Python - beats 99%, true O(n) runtime, no sorting
Intuition\nSorting is an O(n log n) operation, we can do this in O(n) without sorting\n\n# Approach\nIf we have 3 elements, select 1 element, the other 2 can be
# Intuition\nSorting is an O(n log n) operation, we can do this in O(n) without sorting\n\n# Approach\nIf we have 3 elements, select 1 element, the other 2 can be made into that element, guaranteeing a 0 solution.\n\nIf we have 4 elements, by switching 2 we guarantee that the array contains only 2 unique elements, we choose the 2 unique elements that have the least difference between them.\n\nIf we have > 4 elements, ignore temporarily the low score. Notice that the high score is always the minimum element minus the maximum, if we switch a min off, the new high score is the old max minus the new minimum. Therefore, if we get 2 switches, the potential options for lowest high score are by switching off 2 mins, switching off 2 maxes, or switching off a min and a max. Since we\'re only ever switching off 2 numbers from the top or bottom, we can switch them to any middle number and it will guarantee low score = 0. Just need to keep track of the 3 mins and maxes as we iterate through array in O(n) time\n\n# Complexity\n- Time complexity:\nO(n), to iterate through array once\n\n- Space complexity:\nO(1) extra space\n\n# Code\n```\nclass Solution:\n    def minimizeSum(self, nums: List[int]) -> int:\n        if len(nums) == 3:\n            return 0\n        if len(nums) == 4:\n            nums = sorted(nums)\n            return min(nums[3] - nums[2], nums[2] - nums[1], nums[1] - nums[0])\n        min1, min2, min3 = 1000000001, 1000000001, 1000000001\n        max1, max2, max3 = 0, 0, 0\n        for i in nums:\n            if i < min1:\n                min3 = min2\n                min2 = min1\n                min1 = i\n            elif i < min2:\n                min3 = min2\n                min2 = i\n            elif i < min3:\n                min3 = i\n            if i > max1:\n                max3 = max2\n                max2 = max1\n                max1 = i\n            elif i > max2:\n                max3 = max2\n                max2 = i\n            elif i > max3:\n                max3 = i\n        return min(max2 - min2, max1 - min3, max3 - min1)\n```
['Python3']