BinarySearch 0666 Minimum Difference of Extremes

Problem statement

https://binarysearch.com/problems/Minimum-Difference-of-Extremes/

Solution

We can sort numbers and then delete 0/3, 1/2, 2/1, 3/0 biggest/smallest numbers.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, A):
        A = sorted(A)
        n = len(A)
        if n <= 4: return 0
        return min(A[-1] - A[3], A[-2] - A[2], A[-3] - A[1], A[-4] - A[0])

Remark

We can do it in O(n) time as well.