Kth Smallest Pair Sum
Take every pair of different positions i < j in nums and add the two items. Sort all these pair sums from smallest to largest, keeping repeats (two pairs with the same sum count twice). Return the k-th smallest pair sum, where k = 1 is the smallest.
A list of n items has n * (n - 1) / 2 pairs, and k never exceeds that count. nums is not necessarily sorted.
Example 1
nums [1,7,11]
k 2
returns 12
The pair sums are 8, 12 and 18; the 2nd smallest is 12.
Example 2
nums [5,5,2,3]
k 3
returns 7
The pair sums in order are 5, 7, 7, 8, 8, 10, so the 3rd smallest is 7.
Constraints
2 <= len(nums) <= 40-1000 <= nums[i] <= 10001 <= k <= len(nums) * (len(nums) - 1) / 2
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Sorting and searching problems
- Least Truck CapacityMedium
- Merge IntervalsMedium
- Rebuild the LineMedium
- Smallest Divisor Under a LimitMedium
- Spread the TentsMedium
- The One Without a TwinMedium
- The Slot That Comes NextMedium
- All Machines DoneHard