BinarySearch 0174 Median Minimization

Problem statement

https://binarysearch.com/problems/Median-Minimization/

Solution

If we sort numbers and look at the two middle ones, this will be the optimal difference. It is not diffiuclt to prove, but I skip it for the moment.

Complexity

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

Code

class Solution:
    def solve(self, nums):
        nums = sorted(nums)
        n = len(nums)
        return nums[n//2] - nums[n//2 - 1]