Use PriorityQueue O(n)
Intuition\nKeep track of largest 3 and smallest 3 elements, one pass.\nThis can be modifed and become full true O(n) by using 6 variables\n# Approach\n Describe
# Intuition\nKeep track of largest 3 and smallest 3 elements, one pass.\nThis can be modifed and become full true O(n) by using 6 variables\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\nO(n* lg4 * 2 * 2)\nfor each element we need to insert to PQ then remove from PQ each take lg4\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(6)\n\n# Code\n```\nclass Solution {\n    public int minimizeSum(int[] nums) {\n        PriorityQueue<Integer> min = new PriorityQueue<Integer>((a, b)->a-b); \n        PriorityQueue<Integer> max = new PriorityQueue<Integer>((a, b)->b-a);\n        int l=nums[0], r=nums[0];\n        for(int x:nums){\n            min.add(x);\n            max.add(x);\n            l=Math.min(l, x);\n            r=Math.max(r, x);\n            if(min.size()>3)min.poll();\n            if(max.size()>3)max.poll();\n        }\n        int res = Math.min(r-max.peek(), min.peek()-l);\n        min.poll();\n        max.poll();\n        res = Math.min(res, min.peek()-max.peek());\n        return res;\n    }\n}\n```
['Java']