Problem statement

https://binarysearch.com/problems/Minimum-Set-of-Pairs/

Solution

The idea that if we have nubmers a <= b <= c <= d, then it is always optimal to choose as one pair numbers a, d and for another pairs numbers b, c. Then we iterate through pairs (a, d) and then for each of them iterate through inner range [i + 1, j - 1], where we look for the number closest to nums[i] + nums[j], using to pointers technique.

Complexity

It is O(n^3) for time and O(1) for additional space.

Code

class Solution:
    def solve(self, nums):
        nums = sorted(nums)
        n, ans = len(nums), float("inf")
        for i in range(n):
            for j in range(i, n):
                curr = nums[i] + nums[j]
                beg, end = i + 1, j - 1
                while beg < end:
                    pair = nums[beg] + nums[end]
                    ans = min(ans, abs(pair - curr))
                    if pair < curr:
                        beg += 1
                    else:
                        end -= 1
        return ans