<p>You are given an integer array <code>nums</code>.</p>

<ul>
	<li>The <strong>low</strong> score of <code>nums</code> is the <strong>minimum</strong> absolute difference between any two integers.</li>
	<li>The <strong>high</strong> score of <code>nums</code> is the <strong>maximum</strong> absolute difference between any two integers.</li>
	<li>The <strong>score</strong> of <code>nums</code> is the sum of the <strong>high</strong> and <strong>low</strong> scores.</li>
</ul>

<p>Return the <strong>minimum score</strong> after <strong>changing two elements</strong> of <code>nums</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,4,7,8,5]</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>Change <code>nums[0]</code> and <code>nums[1]</code> to be 6 so that <code>nums</code> becomes [6,6,7,8,5].</li>
	<li>The low score is the minimum absolute difference: |6 - 6| = 0.</li>
	<li>The high score is the maximum absolute difference: |8 - 5| = 3.</li>
	<li>The sum of high and low score is 3.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,4,3]</span></p>

<p><strong>Output:</strong> <span class="example-io">0</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>Change <code>nums[1]</code> and <code>nums[2]</code> to 1 so that <code>nums</code> becomes [1,1,1].</li>
	<li>The sum of maximum absolute difference and minimum absolute difference is 0.</li>
</ul>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

import heapq
class Solution:
    """
    There are basically 3 possibilities:
    1. change min and min2 to min3
    2. change min to min2, and max to max2
    3. change max and max2 to max3

    That will always leave the minimum difference to 0.
    What is the best maximum difference then?
    find minx, maxx
    compare:
    1. min3, max
    2. min2, max2
    3. min, max3

    Trivial: O(n log n)
    sort and check the difference.

    Better worst case complexity: O(n)
    find min1, min2, min3 and max...
    
    we can use a heap for this
    """
    def minimizeSum(self, nums: List[int]) -> int:
        max1, max2, max3 = float("-inf"), float("-inf"), float("-inf")
        min1, min2, min3 = float("inf"), float("inf"), float("inf")
        for n in nums:
            if n > max1:
                max2, max3 = max1, max2
                max1 = n

            elif n > max2:
                max3 = max2
                max2 = n

            elif n > max3:
                max3 = n

            if n < min1:
                min2, min3 = min1, min2
                min1 = n

            elif n < min2:
                min3 = min2
                min2 = n

            elif n < min3:
                min3 = n

        return min(max3 - min1, max2 - min2, max1 - min3)
241