Given an array nums, you are allowed to choose one element of nums and change it by any value in one move.
Return the minimum difference between the largest and smallest value of nums after perfoming at most 3 moves.
 
Example 1:
Input: nums = [5,3,2,4]
Output: 0
Explanation: Change the array [5,3,2,4] to [2,2,2,2].
The difference between the maximum and minimum is 2-2 = 0.
Example 2:
Input: nums = [1,5,0,10,14]
Output: 1
Explanation: Change the array [1,5,0,10,14] to [1,1,0,1,1]. 
The difference between the maximum and minimum is 1-0 = 1.

Example 3:
Input: nums = [6,6,0,1,1,4,6]
Output: 2

Example 4:
Input: nums = [1,5,6,14,15]
Output: 1

 
Constraints:

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Difficulty: interview

Starter code:

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0
        else:
            # nums = sorted(nums)
            nums.sort()
            threeZero = nums[-1] - nums[3]
            twoOne = nums[-2] - nums[2]
            oneTwo = nums[-3] - nums[1]
            zeroThree = nums[-4] - nums[0]
            return min(threeZero,twoOne,oneTwo,zeroThree)

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        i = 3
        j = n - 1
        if n <= 4:
            return 0
        ans = float('inf')
        while i >= 0 and j >= 0:
            ans = min(ans,abs(nums[i] - nums[j]))
            i -= 1
            j -= 1
        return ans

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        a = nums
        if len(a) <= 4:
            return 0
        a.sort()
        print(a)
        return min(a[-1] - a[3], a[-2] - a[2], a[-3] - a[1], a[-4] - a[0])

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        #0,1,4,5,10
        N = len(nums)-1
        if N < 3:
            return 0
        minVal = 2**32
        nums.sort()
        
        for i in range(4):
            minVal = min(minVal, nums[N-3+i]-nums[i])
            
        return minVal

class Solution:
    # don't even sort - YOU READ IT!!!!
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) < 5:
            return 0
        
        max4 = max3 = max2 = max1 = -float('inf')
        min4 = min3 = min2 = min1 = float('inf')

        for i in nums:
            if i > max1: 
                max4 = max3
                max3 = max2
                max2 = max1
                max1 = i
            elif i > max2 and i <= max1:
                max4 = max3
                max3 = max2
                max2 = i
            elif i > max3 and i <= max2:
                max4 = max3
                max3 = i
            elif i > max4 and i <= max3:
                max4 = i
                
            if i < min1: 
                min4 = min3
                min3 = min2
                min2 = min1
                min1 = i
            elif i < min2 and i >= min1:
                min4 = min3
                min3 = min2
                min2 = i
            elif i < min3 and i >= min2:
                min4 = min3
                min3 = i
            elif i < min4 and i >= min3:
                min4 = i
            #print(str([min1, min2, min3, min4]))
            #print(str([max4, max3, max2, max1]))
        
        smallest_diff = max4 - min1
        diff = max3 - min2
        if smallest_diff > diff:
            smallest_diff = diff
        diff = max2 - min3
        if smallest_diff > diff:
            smallest_diff = diff
        diff = max1 - min4
        if smallest_diff > diff:
            smallest_diff = diff
        return smallest_diff
    '''
    #original submission
    def minDifference(self, nums: List[int]) -> int:

        if len(nums) < 5: 
            return 0
        
        a = sorted(nums)
        
        H = len(nums) - 4
        L = 0
        lowest_diff = None
        for i in range(4):
            diff = a[H] - a[L]
            if lowest_diff == None or lowest_diff > diff:
                lowest_diff = diff
            H += 1
            L += 1
        
        return lowest_diff
    '''
    '''
    # faster and cleaner - same as original solution
    def minDifference(self, nums: List[int]) -> int:

        if len(nums) < 5: 
            return 0
        
        nums = sorted(nums)
        
        N = len(nums)
        lowest_diff = None
        for i in range(4):
            diff = nums[N-(4-i)] - nums[i]
            if lowest_diff == None or lowest_diff > diff:
                lowest_diff = diff
        
        return lowest_diff
    '''
    '''
    #original attempt - sort into a sort of binary search
    def minDifference(self, nums: List[int]) -> int:
        
        N = len(nums)
        
        # any array of length 4 or less can have all elements mapped to same value
        if len(nums) < 5: 
            return 0
        
        # sort 
        a = sorted(nums)
        
        # compare 'new' low/highs to an updated median
        L = 0
        H = len(nums) - 1
        # counts for those remapped from each side
        Lc = 0
        Hc = 0
        for i in range(3):
            m = int((L + H + 2)/2)
            M = a[m]
            low = a[L]
            high = a[H]
            lowDiff = M - low
            highDiff = high - M
            # implies we should set the lowest value to the final median
            if lowDiff > highDiff:
                L += 1
                Lc += 1
            # implies we should set the highest value to the final median
            elif lowDiff < highDiff:
                H -= 1
                Hc += 1
            # implies the differences are the same - pick the side with a higher count
            else:
                if Hc > Lc:
                    H -= 1
                    Hc += 1
                else:
                    L += 1
                    Lc += 1
                    
        return a[H] - a[L]
    '''

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        i = 3
        j = n - 1
        ans = float('inf')
        if n <= 4:
            return 0
        while i >= 0 and j >= 0:
            ans = min(ans,abs(nums[i] - nums[j]))
            i -= 1
            j -= 1
        return ans

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0
        nums.sort()
        return min(
            nums[-1] - nums[3],
            nums[-2] - nums[2],
            nums[-3] - nums[1],
            nums[-4] - nums[0],
        )

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        nums.sort()
        return min(x - y for x, y in zip(nums[-4:], nums[:4]))

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0
        elif len(nums) == 5:
            nums_sorted = sorted(nums)
            diff = []
            for i in range(1, len(nums)):
                diff.append(nums_sorted[i] - nums_sorted[i-1])
            return min(diff)
        else:
            largest_four = []
            smallest_four = []
            for n in nums:
                if len(largest_four) < 4:
                    heapq.heappush(largest_four, n)
                    heapq.heappush(smallest_four, -n)
                else:
                    heapq.heappushpop(largest_four, n)
                    heapq.heappushpop(smallest_four, -n)
            smallest_four = sorted([-x for x in smallest_four])
            largest_four = sorted(largest_four)

            diff_arr = [largest_four[0] - smallest_four[0],
                        largest_four[3] - smallest_four[3],
                        largest_four[1] - smallest_four[1],
                        largest_four[2] - smallest_four[2]]

        return min(diff_arr)


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        
        if n<=3:
            return 0
        
        nums.sort()
        return min(nums[n-4+i]-nums[i] for i in range(4))

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        ans = float('inf')
        nums.sort()
        if n <= 4:
            return 0
        i = 3
        j = n - 1
        
        while i >= 0 and j >= 0:
            ans = min(ans,abs(nums[j] - nums[i]))
            i -= 1
            j -= 1
        return ans

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0
        max_3 = sorted(nums[:4], reverse=True)
        min_3 = sorted(nums[:4])
        for i in range(4, len(nums)):
            max_3.append(nums[i])
            max_3.sort(reverse=True)
            max_3.pop()
            min_3.append(nums[i])
            min_3.sort()
            min_3.pop()
        return min([max_3[i] - min_3[3 - i] for i in range(4)])

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 5: return 0
        nums.sort()
        return min([ nums[n-4+i] - nums[i] for i in range(4)])
        
        #return min(a - b for a,b in zip(heapq.nlargest(4, A), heapq.nsmallest(4, A)[::-1]))


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        nums.sort()
        l = [y - x for x, y in zip(nums[:4], nums[-4:])]
        return min(l)


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 3:
            return 0
        nums.sort()
        x = 0
        y = len(nums) - 1
        arr = []
        while x < y:
            arr.append(nums[x])
            arr.append(nums[y])
            x += 1
            y -= 1
        if x == y:
            arr.append(nums[x])
        arr.sort()
        self.ans = float('inf')
        self.min_diff(0, len(arr) - 1, arr, 3)
        return self.ans
        
    def min_diff(self, i, j, arr, depth):
        if depth == 0:
            self.ans = min(self.ans, arr[j] - arr[i])
            return
        self.min_diff(i + 1, j, arr, depth - 1)
        self.min_diff(i, j - 1, arr, depth - 1)


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        # O(n) time, O(1) space since mins and maxs are at most 4 elements
        if len(nums) <= 4:
            return 0
        
        # find the smallest 4 numbers and largest 4 numbers
        mins, maxs = nums[:4], nums[:4]
        for num in nums[4:]:
            mins.append(num)
            mins.sort()
            mins.pop()
            maxs.append(num)
            maxs.sort(reverse = True)
            maxs.pop()
        maxs = maxs[::-1]
        '''
\t\tmins[i] maxs[j]
        i j
        0 0 # change the largest 3 numbers to the 4-th largest, smallest numbers unchanged
        1 1 # change the smallest number to the 2nd smallest, change the 2 largest to 3rd largest
        2 2 # change the smallest 2 numbers to 3rd smallest, change the largest to 2nd largest
        3 3 # change the smallest 3 numbers to 4th smallest,largest number unchanged
        '''
        return min(maxs[i] - mins[i] for i in range(4))
'''
Input 1: [1,5,0,10,14], all maxs and mins are not overlapped
maxs [1, 5, 10, 14]
mins [0, 1, 5, 10]
diff [1, 4, 5, 4]

Input 2: [1,1,2,3,4], maxs and mins are overlapped
maxs [1, 2, 3, 4]
mins [1, 1, 2, 3]
diff [0, 1, 1, 1]
'''    

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) < 5: return 0
        nums = sorted(nums)
        print (nums)
        n = len(nums)-1
        return min(nums[n] - nums[3], nums[n-1] - nums[2], nums[n-2] - nums[1],nums[n-3] - nums [0])
            


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        nums = sorted(nums)
        if len(nums)<=4:
            return 0
        print(nums)
        return min(nums[-1]-nums[3], 
                   nums[-4]-nums[0],
                  nums[-2]-nums[2],
                  nums[-3]-nums[1]
                  )

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0
        nums = sorted(nums)
        l, r = 0, len(nums)-1
        res = nums[-1]-nums[0]
        for i in range(0, 4):
            res = min(res, nums[-4+i]-nums[i])
        return res

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4: #if only one number is left difference is 0
            return 0
        nums.sort()
        return min(nums[-1-i] - nums[3-i] for i in range(4))
                #nums[-1 -0/1/2/3] is getting the largest 4 numbers
                #nums[3 - 0/1/2/3] is getting the smallest 4 numbers


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums)<=4: 
            return 0
        maxHeap, minHeap = [],[]
        import heapq
        for e in nums:
            heappush(maxHeap,e)
            heappush(minHeap,e*-1)
            if len(maxHeap)>4:
                heappop(maxHeap)
                heappop(minHeap)
        minHeap = sorted([-1*e for e in minHeap]) #in ascending order
        res = float('inf')
        for i in range(4):
            
            res = min(res, heappop(maxHeap)-minHeap[i])
            
        
        return res

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        
        if len(nums) <= 4: return 0
        nums.sort()
        return min(nums[-1] - nums[3], nums[-2] - nums[2], nums[-3] - nums[1], nums[-4] - nums[0])


import copy
from typing import List
import numpy

import sys
# Definition for a binary tree node.
# Definition for a binary tree node.
class Solution:
  def minDifference(self, nums: List[int]) -> int:
    result = 0

    if len(nums) <= 4:
      return 0

    nums.sort()
    result = sys.maxsize
    result = min(result, nums[-1] - nums[3])
    result = min(result, nums[-2] - nums[2])
    result = min(result, nums[-3] - nums[1])
    result = min(result, nums[-4] - nums[0])
    return result



class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0
        nums.sort()
        r1 = max(nums[0:-3]) - min(nums[0:-3])
        r2 = max(nums[1:-2]) - min(nums[1:-2])
        r3 = max(nums[2:-1]) - min(nums[2:-1])
        r4 = max(nums[3:]) - min(nums[3:])
        
        return min(r1, r2, r3, r4)

from heapq import heappush, heappop

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        
        max_h = []
        min_h = []
        
        for i in nums:
            heappush(max_h, i)
            heappush(min_h, -i)
            
            if len(max_h) > 4:
                heappop(max_h)
                heappop(min_h)

            
                
        min_h = [-item for item in min_h]
        
        max_h.sort()
        min_h.sort()
        
        return min([max_h[i] - min_h[i] for i in range(len(max_h))])

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        nums.sort()
        return min(a-b for a, b in zip(nums[-4:],nums[:4]))

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        nums.sort()
        result = nums[-1] - nums[0]
        x = min(4, len(nums))
        for i in range(x):
            curr = nums[-x + i] - nums[i]
            result = min(result, curr)
        return result


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        nums.sort()
        if len(nums) <= 4:
            return 0
        res = float('inf')
        n = len(nums)
        for i in range(4):
            res = min(res, nums[n-4+i] - nums[i])
        return res

class Solution:
    def minDifference(self, A: List[int]) -> int:
        if len(A) <= 4:
            return 0
        
        A = sorted(A)
        res = math.inf
        for i in range(4):
            res = min(res, A[len(A) - i - 1] - A[3 - i])
        return res


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums)<=4:
            return 0
        
        nums.sort()
        print(nums)
        cur = max(nums)-min(nums)
        
        h1 = nums[0]
        nums[0]=nums[-1]
        if max(nums)-min(nums)<cur:
            cur = max(nums)-min(nums)
        nums[0] = h1
        
        h1,h2 = nums[0],nums[1]
        nums[0],nums[1]=nums[-1],nums[-1]
        if max(nums)-min(nums)<cur:
            cur = max(nums)-min(nums)
        nums[0],nums[1] = h1,h2
        
        h1,h2,h3 = nums[0],nums[1],nums[2]
        nums[0],nums[1],nums[2]=nums[-1],nums[-1],nums[-1]
        if max(nums)-min(nums)<cur:
            cur = max(nums)-min(nums)
        nums[0],nums[1],nums[2] = h1,h2,h3
        
        h1,h2,h3 = nums[-1],nums[-2],nums[-3]
        nums[-1],nums[-2],nums[-3]=nums[0],nums[0],nums[0]
        if max(nums)-min(nums)<cur:
            cur = max(nums)-min(nums)
        nums[-1],nums[-2],nums[-3] = h1,h2,h3
        
        h1,h2 = nums[-1],nums[-2]
        nums[-1],nums[-2]=nums[0],nums[1]
        if max(nums)-min(nums)<cur:
            cur = max(nums)-min(nums)
        nums[-1],nums[-2] = h1,h2
        
        h1 = nums[-1]
        nums[-1]=nums[0]
        if max(nums)-min(nums)<cur:
            cur = max(nums)-min(nums)
        nums[-1] = h1
        
        ############################################################
        
        h1,h2,h3 = nums[0],nums[1],nums[-1]
        nums[0],nums[1],nums[-1] = nums[2],nums[2],nums[2]
        if max(nums)-min(nums)<cur:
            cur = max(nums)-min(nums)
        nums[0],nums[1],nums[-1] = nums[-2],nums[-2],nums[-2]
        if max(nums)-min(nums)<cur:
            cur = max(nums)-min(nums)
        nums[0],nums[1],nums[-1] = h1,h2,h3
        
        h1,h2,h3 = nums[0],nums[-1],nums[-2]
        nums[0],nums[-1],nums[-2] = nums[1],nums[1],nums[1]
        if max(nums)-min(nums)<cur:
            cur = max(nums)-min(nums)
        nums[0],nums[-1],nums[-2] = nums[-3],nums[-3],nums[-3]
        if max(nums)-min(nums)<cur:
            cur = max(nums)-min(nums)
        nums[0],nums[-1],nums[-2] = h1,h2,h3
        
        return cur

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        if n<=4: return 0
        
        nums.sort()
        res = float('inf')
        for i in range(4):
            l = nums[i]
            r = nums[n-1-3+i]
            res = min(nums[n-1-3+i]-nums[i], res)
        return res

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        nums.sort()
        return min(b - a for a, b in zip(nums[:4], nums[-4:]))    


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 5:
            return 0
        nums.sort()
        return min(nums[-1] - nums[3], nums[-2]-nums[2], nums[-3]-nums[1], nums[-4]-nums[0])

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        ans = float('inf')
        i = 3
        j = n - 1
        if n <= 4:
            return 0
        
        while i >= 0 and j >= 0:
            ans = min(ans,nums[j] - nums[i])
            i -= 1
            j -= 1
        return ans

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums)<4: return 0
        from collections import Counter
        dic = sorted(Counter(nums).items())
        res = [dic[0][0]]
        # print(dic)
        if dic[0][1]>3:
            res += [dic[0][0]] * 3
        elif dic[0][1]==3:
            res += [dic[0][0]] * 2
            res.append(dic[1][0])
        elif dic[0][1]==2:
            res.append(dic[0][0])
            res.append(dic[1][0])
            if dic[1][1]>1:
                res.append(dic[1][0])
            else:
                res.append(dic[2][0])
        else:
            res.append(dic[1][0])
            if dic[1][1]>2:
                res.append(dic[1][0])
                res.append(dic[1][0])
            elif dic[1][1]==2:
                res.append(dic[1][0])
                res.append(dic[2][0])
            else:
                res.append(dic[2][0])
                if dic[2][1]>1:
                    res.append(dic[2][0])
                else:
                    res.append(dic[3][0])
        if dic[-1][1]>3:
            res = [dic[-1][0]-res[i] for i in range(4)]
        elif dic[-1][1]==3:
            res = [dic[-1][0]-res[i] for i in range(1,4)] + [dic[-2][0]-res[0]]
        elif dic[-1][1]==2:
            tmp = [dic[-1][0]-res[i] for i in range(2,4)]
            if dic[-2][1]>1:
                tmp += [dic[-2][0]-res[0]] + [dic[-2][0]-res[1]]
            else:
                tmp += [dic[-3][0]-res[0]] + [dic[-2][0]-res[1]]
            res = tmp
        else:
            tmp = [dic[-1][0]-res[3]]
            if dic[-2][1]>2:
                tmp += [dic[-2][0]-res[i] for i in range(3)]
            elif dic[-2][1]==2:
                tmp += [dic[-2][0]-res[i] for i in range(1,3)]
                tmp += [dic[-3][0]-res[0]]
            else:
                tmp += [dic[-2][0]-res[2]]
                tmp += [dic[-3][0]-res[1]]
                if dic[-3][1]>1:
                    tmp += [dic[-3][0]-res[0]]
                else:
                    tmp += [dic[-4][0]-res[0]]
            res = tmp
        return min(res)


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 5:
            return 0
        # nums.sort()
        # return min(nums[-4]-nums[0], nums[-3]-nums[1], nums[-2]-nums[2], nums[-1]-nums[3])
        
        l = []
        h = []
        
        for c in nums:
            heapq.heappush(l, -c)
            if len(l) > 4:
                heapq.heappop(l)
            heapq.heappush(h, c)
            if len(h) > 4:
                heapq.heappop(h)
        
        l = [-c for c in l]
        l.sort()
        h.sort()
        
        return min(h[0]-l[0], h[1]-l[1], h[2]-l[2], h[3]-l[3])

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        '''
        s1, s2, s3 = l1 - s4
        s1, s2, l1 = l2 - s3
        s1, l1, s2 = l2 - s3
        s1, l1, l2 = l3 - s2
        l1, s1, s2 = l2 - s3
        l1, s1, l2 = l3 - s2
        l1, l2, s1 = l3 - s2
        l1, l2, l3 = l4 - s1
        '''
        if len(nums) <= 4:
            return 0
        nums.sort()
        return min([
            nums[-1] - nums[3],
            nums[-2] - nums[2],
            nums[-3] - nums[1],
            nums[-4] - nums[0]
        ])


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        ans = float('inf')
        if n <= 4:
            return 0
        i = 3
        j = n - 1
        while i >= 0 and j >= 0:
            ans = min(ans,nums[j] - nums[i])
            i -= 1
            j -= 1
        return ans

import heapq

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        largest = heapq.nlargest(4, nums)
        smallest = heapq.nsmallest(4, nums)
        
        m = 10**10
        n = len(largest)
        for i in range(n):
            m = min(m, largest[i] - smallest[n - 1 -i])
        return max(m, 0)

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        # 1. replace 3 of the elements < num
        # 2. replace 3 of the elements > num
        # Calculate the difference between min and max
        n = len(nums)
        if n < 5: return 0
        ans = float('inf')
        nums.sort()
        for i in range(4):
            ans = min(ans, nums[n-4+i] - nums[i])
        return ans

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        nums.sort()
        return min(abs(nums[0] - nums[-4]),abs(nums[2] - nums[-2]),abs(nums[1] - nums[-3]),abs(nums[3] - nums[-1])) if len(nums) > 4 else 0        

        # 4 cases 


#81,48,48 |31, 48, 48

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        l = len(nums)
        
        biggest = nums[:min(4, l)]
        smallest = nums[:min(4, l)]
        for i in range(4, l):
            num = nums[i]
            biggest.append(num)
            smallest.append(num)
            
            biggest.remove(min(biggest))
            smallest.remove(max(smallest))
                
        
        # print(simplified)
        if len(biggest) < 4:
            return 0
        
        bfs = [(sorted(biggest), sorted(smallest), 0)]
        
        opt = max(biggest) - min(smallest)
        while bfs:
            new_biggest, new_smallest, changes = bfs.pop(0)
            
            if changes == 3:
                # print(current)
                opt = min(
                    opt,
                    max(new_biggest) - min(new_smallest)
                )
                continue
            
            bfs.append((new_biggest[:-1], list(new_smallest), changes + 1))
            bfs.append((list(new_biggest), new_smallest[1:], changes + 1))
            
        return opt
        # return max(b) - min(s)
        
        
            
            


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        return min(b-a for a,b in zip(sorted(nums)[:4],sorted(nums)[-4:]))

class Solution:
    def _util(self, nums):
        min_heap, max_heap = [], []
        for i, x in enumerate(nums):
            heapq.heappush(min_heap, (x, i))
            if len(min_heap) > 4:
                heapq.heappop(min_heap)
            heapq.heappush(max_heap, (-x, i))
            if len(max_heap) > 4:
                heapq.heappop(max_heap)
        return sorted([x for x, i in set(min_heap + [(-x, i) for x, i in max_heap])])

    def minDifference(self, nums: List[int]) -> int:
        lst = sorted(nums)
        result = lst[-1] - lst[0]
        x = min(4, len(lst))
        for i in range(x):
            curr = lst[-x + i] - lst[i]
            result = min(result, curr)
        return result


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        ans = float('inf')
        nums.sort()
        i = 3
        j = n - 1
        if n <= 4:
            return 0
        while i >= 0 and j >= 0:
            ans = min(ans,nums[j] - nums[i])
            i -= 1
            j -= 1
        return ans

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        l=nums[::]
        l.sort()
        if len(l)<=4:
            return 0
        else:
            return min(abs(l[-4]-l[0]),abs(l[-1]-l[3]),abs(l[2]-l[-2]),abs(l[-3]-l[1]))


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0
        
        ans = float('inf')
        nums.sort()
        for i in range(4):
            ans = min(ans, nums[-4 + i] - nums[i])
        return ans


'''
[5,3,2,4]
[1,5,0,10,14]
[6,6,0,1,1,4,6]
[1,5,6,14,15]
'''

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        
        n = len(nums)
        
        if n < 5:
            return 0
        
        nums.sort()
        
        diff = n - 4
        ans = math.inf
        for i in range(0, n-diff):
            ans = min(ans, nums[i+diff] - nums[i])
            
        return ans


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) < 5:
            return 0

        nums.sort()
        candidates = (
            nums[-1] - nums[3],
            nums[-2] - nums[2],
            nums[-3] - nums[1],
            nums[-4] - nums[0]
        )

        return min(candidates)


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) < 5:
            return 0
        ns = sorted(nums)
        mindif = ns[-4] - ns[0]
        for i in range(1,4):
            if ns[i-4] - ns[i] < mindif:
                mindif = ns[i-4] - ns[i]
        return mindif

import heapq
class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0
        if len(nums) == 5:
            nums.sort()
            return min(b-a for a,b in zip(nums, nums[1:]))
        a = heapq.nsmallest(4, nums)
        b = heapq.nlargest(4, nums)
        arr = a + b
        arr.sort()
        return min(
            arr[4]-arr[0], arr[5]-arr[1], arr[6]-arr[2], arr[7]-arr[3], 
        )


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums)<=4: 
            return 0
        nums.sort()
        n = len(nums)
        res = min(nums[n-4]-nums[0],nums[n-3]-nums[1],nums[n-2]-nums[2],nums[n-1]-nums[3])
        return res

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        
        if len(nums) <=4:
            return 0
        nums.sort()
        a = min([nums[-4] - nums[0],nums[-1] - nums[3],nums[-3] - nums[1], nums[-2] - nums[2]])
        return a


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 3:
            return 0
        nums.sort()
        # remove smallest 3
        min_diff = nums[-1] - nums[3]
        
        for i in range(3):
            min_diff = min(min_diff, nums[-2-i] - nums[3-i-1])
        
        return min_diff    


class Solution:
    def _util(self, nums):
        min_heap, max_heap = [], []
        for i, x in enumerate(nums):
            heapq.heappush(min_heap, (x, i))
            if len(min_heap) > 4:
                heapq.heappop(min_heap)
            heapq.heappush(max_heap, (-x, i))
            if len(max_heap) > 4:
                heapq.heappop(max_heap)
        return sorted([x for x, i in set(min_heap + [(-x, i) for x, i in max_heap])])

    def minDifference(self, nums: List[int]) -> int:
        lst = self._util(nums) if len(nums) > 100 else sorted(nums)
        result = lst[-1] - lst[0]
        x = min(4, len(lst))
        for i in range(x):
            curr = lst[-x + i] - lst[i]
            result = min(result, curr)
        return result


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        l = len(nums)
        if l < 5:
            return 0
        nums.sort()
        min = 99999999999
        if min > nums[l-1] - nums[3]:
            min = nums[l-1] - nums[3]
        if min > nums[l-2] - nums[2]:
            min =nums[l-2] - nums[2]
        if min > nums[l-3] - nums[1]:
            min =nums[l-3] - nums[1]
        if min > nums[l-4] - nums[0]:
            min =nums[l-4] - nums[0]
        return min


class Solution:
    def minDifference(self, A: List[int]) -> int:
        if len(A) <= 4:
            return 0
        
        max_vals = [0] * 4
        min_vals = [math.inf] * 4
        for a in A:
            for i in range(4):
                if a > max_vals[i]:
                    max_vals[i+1:] = max_vals[i:-1]
                    max_vals[i] = a
                    break
            for i in range(4):
                if a < min_vals[i]:
                    min_vals[i+1:] = min_vals[i:-1]
                    min_vals[i] = a
                    break
        res = math.inf
        for i in range(4):
            res = min(res, max_vals[i] - min_vals[3 - i])
        return res


class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return  0 
        
        nums.sort()
        l = nums[0:4]
        r = nums[-4:]
        p = 0 
        res = float('inf')
        while p < 4:
            res = min(res, r[p] - l[p])
            p += 1
            
        return res
        


import heapq
class Solution:
    def minDifference(self, nums: List[int]) -> int:
        
        if len(nums) <= 4:
            return 0
        
        minheap = []
        maxheap = []
        
        for j, num in enumerate(nums):
            
            if len(minheap) < 4:
                heapq.heappush(minheap, -num)
            else:
                x = heapq.heappop(minheap)
                if x > -num:
                    heapq.heappush(minheap, x)
                else:
                    heapq.heappush(minheap, -num)
                    
            if len(maxheap) < 4:
                heapq.heappush(maxheap, num)
            else:
                x = heapq.heappop(maxheap)
                if x > num:
                    heapq.heappush(maxheap, x)
                else:
                    heapq.heappush(maxheap, num)
        
        minheap = [-x for x in minheap]
        minheap.sort()
        maxheap.sort()
        
        diff = [maxheap[-1]-minheap[-1], 
                maxheap[0]-minheap[0],
                maxheap[-2]-minheap[2],
                maxheap[-3]-minheap[1]]
        
        return min(diff)
                


class Solution:
    #original submission
    def minDifference(self, nums: List[int]) -> int:

        if len(nums) < 5: 
            return 0
        
        a = sorted(nums)
        
        H = len(nums) - 4
        L = 0
        lowest_diff = None
        for i in range(4):
            diff = a[H] - a[L]
            if lowest_diff == None or lowest_diff > diff:
                lowest_diff = diff
            H += 1
            L += 1
        
        return lowest_diff
    '''
    # faster and cleaner
    def minDifference(self, nums: List[int]) -> int:

        if len(nums) < 5: 
            return 0
        
        nums = sorted(nums)
        
        N = len(nums)
        lowest_diff = None
        for i in range(4):
            diff = nums[N-(4-i)] - nums[i]
            if lowest_diff == None or lowest_diff > diff:
                lowest_diff = diff
        
        return lowest_diff
    '''
    '''
    #original attempt
    def minDifference(self, nums: List[int]) -> int:
        
        N = len(nums)
        
        # any array of length 4 or less can have all elements mapped to same value
        if len(nums) < 5: 
            return 0
        
        # sort 
        a = sorted(nums)
        
        # compare 'new' low/highs to an updated median
        L = 0
        H = len(nums) - 1
        # counts for those remapped from each side
        Lc = 0
        Hc = 0
        for i in range(3):
            m = int((L + H + 2)/2)
            M = a[m]
            low = a[L]
            high = a[H]
            lowDiff = M - low
            highDiff = high - M
            # implies we should set the lowest value to the final median
            if lowDiff > highDiff:
                L += 1
                Lc += 1
            # implies we should set the highest value to the final median
            elif lowDiff < highDiff:
                H -= 1
                Hc += 1
            # implies the differences are the same - pick the side with a higher count
            else:
                if Hc > Lc:
                    H -= 1
                    Hc += 1
                else:
                    L += 1
                    Lc += 1
                    
        return a[H] - a[L]
    '''

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        # 找到最小的3个和最大的3个
        
        if len(nums) <= 4: return 0
        
        nums.sort()
        a1,a2,a3,a4 = nums[:4]
        print(a1,a2,a3,a4)
        b4,b3,b2,b1 = nums[-4:]
        
        return min(b4-a1, b3-a2, b2-a3, b1-a4)