Problem statement

https://binarysearch.com/problems/Pair-Matches-Larger-Than-Target/

Solution

Sort numbers, then if we want to make k pairs we need to choose k smallest and biggest values with equal index gaps. Then use binary search to find k.

Complexity

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

Code

class Solution:
    def solve(self, A, target):
        A = sorted(A)
        n = len(A)
        def check(k):
            return min(A[i + n - k] - A[i] for i in range(k))

        beg, end = 0, len(A)//2 + 1
        while beg + 1 < end:
            mid = (beg + end) >> 1
            if check(mid) >= target:
                beg = mid
            else:
                end = mid
        return beg