[Leetcode] 2616. Minimize the Maximum Difference of Pairs

https://leetcode.com/problems/minimize-the-maximum-difference-of-pairs/description/?envType=daily-question&envId=2025-06-13

initial

so i immediately knew we had to sort the given list to find pairs but i wasnt sure how to calculate each pair's min difference. Like wat the logic would be.

I thought about using a max heap to pop any big difference value from our heap whenever we check for nums[i] and nums[i-1] but that logic seemed incorrect for case like [1,1,1]. You're not trying to find "each pair's min difference" in isolation, and then somehow combine them. thats wrong thinking

Instead, the problem asks you to find the smallest possible value X, such that you can pick p pairs where every single one of those p pairs has a difference |a - b| <= X.

So wat if we use binary search to guess the threshold value, which is our answer? We greedily check if we can form a pair which difference is less than our equal to this guess threshold value and if we can form a pair, we increment count and increment idx by 2, not 1. This is cuz the current index cannot be reused to form another pair.

sol

btw the right val can be nums[-1] - nums[0]

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        # 1,1,2,3,7,10
        # state for each node is
        # 1) take previous state and form a pair
        # 2) continue for next state to consider this current node as pair

        nums.sort()
        n=len(nums)
        ans=-1

        def binary_search():
            nonlocal n,ans
            left,right=0,int(10e9)
            while left<right:
                mid =left+(right-left)//2
                if greedy(mid)>=p:
                    ans=mid
                    right=mid
                else:
                    left=mid+1

        def greedy(guess):
            nonlocal n,nums
            idx=1
            count=0
            while idx<n:
                if abs(nums[idx]-nums[idx-1])<=guess:
                    count+=1
                    idx+=2
                else:
                    idx+=1
            return count 
            
        binary_search()
        return ans

complexity

n log n time of sort dominates time

yes, lets look at bs which has time of O(log(RangeSize)). log(109) is around 30. if number of bits is K, we can set bs time as o(k). but if we set right as nums[-1]-nums[0], its practically just constant time

and the greedy approach is o(n)

so n log n + n

n space cuz of nums?

actually When discussing space complexity, we typically focus on the additional (auxiliary) space used by the algorithm, not the space taken by the input itself.
so itsj ust constant space