Top K Pair Sums From One Array
Google● MediumNEW GRADONSITE INTERVIEWProblem statement
Given an integer array nums, every pair of distinct indices i < j produces the sum nums[i] + nums[j].
Return the k largest pair sums in nonincreasing order. Distinct index pairs are distinct combinations, so equal values and equal sums retain their multiplicity.
Function
topKPairSums(nums: int[], k: int) → long[]Examples
Example 1
nums = [1,2,3]k = 2return = [5,4]The pair sums are 5 from 2+3, 4 from 1+3, and 3 from 1+2.
Example 2
nums = [4,4,1]k = 3return = [8,5,5]The two different index pairs containing 1 both contribute a sum of 5.
Example 3
nums = [-5,-1,2,3]k = 4return = [5,2,1,-2]The four largest sums are 2+3, -1+3, -1+2, and -5+3.
Constraints
2 <= nums.length <= 100000.-1000000000 <= nums[i] <= 1000000000.1 <= k <= min(100000, nums.length * (nums.length - 1) / 2).