Kth Smallest Pair Sum

Problem

Given nums and k, return the k-th smallest sum of a pair at distinct indices, where every unordered pair forms one entry.

Binary search the sum value and count how many pairs have a sum at most the candidate using a two-pointer sweep over the sorted array. Assume k does not exceed the number of pairs.

Hint

For a fixed left pointer, every right pointer down to the first valid one forms a pair under the limit.

Test cases

case 1

in: [[1,1,1],2]

expected: 2

case 2

in: [[1,2,3,4],4]

expected: 5

case 3

in: [[1,6,1],3]

expected: 7

case 4

in: [[1,2],1]

expected: 3

case 5

in: [[5,6,7],2]

expected: 12

Starter codePython

def kth_smallest_pair_sum(nums, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor