python - O(n)/O(1) - No Sorting/No heap
Intuition\n\nThere are only 3 possibilities:\n- change the two smallest values: score becomes largest minus third smallest\n- change the two largest values: sco
# Intuition\n\nThere are only 3 possibilities:\n- change the two smallest values: score becomes largest minus third smallest\n- change the two largest values: score becomes third largest minus smallest\n- change the largest and smallest values: score becomes second largest minus second smallest\n\nWhen we change a variable, we change it to some other value that remains in the array (we do not care about this value).\n\nTherefore we only care about the 3 smallest and 3 largest values and we can get them in $O(n)$ and $O(1)$.\n\n# Approach\n\nWe go though the array and keep track of the 3 smallest and 3 largest values. After this we return the minimum combination.\n\n# Complexity\n- Time complexity:\n$O(n)$ - We go through the array once.\n\n- Space complexity:\n$O(1)$ - We only use constant extra space for the 6 variables of interest.\n\n# Code\n```python3 []\nclass Solution:\n    def minimizeSum(self, nums: List[int]) -> int:\n        \n        min1, min2, min3, max1, max2, max3 = float(\'inf\'), float(\'inf\'), float(\'inf\'), 0, 0, 0\n        for i, num in enumerate(nums):\n            if num <= min1:\n                min3 = min2\n                min2 = min1\n                min1 = num\n            elif num <= min2:\n                min3 = min2\n                min2 = num\n            elif num < min3:\n                min3 = num\n            if num >= max1:\n                max3 = max2\n                max2 = max1\n                max1 = num\n            elif num >= max2:\n                max3 = max2\n                max2 = num\n            elif num > max3:\n                max3 = num\n\n        return min(max2 - min2, max1 - min3, max3 - min1)\n```
['Python3']