FastPrepK Smallest Pair Sums

K Smallest Pair Sums

Google logoGoogle● MediumNEW GRADPHONE SCREEN
Learn

Problem statement

Given two integer arrays arr1 and arr2, both sorted in nondecreasing order, consider every index pair (i, j) and its sum arr1[i] + arr2[j].

Return the k smallest pair sums in nondecreasing order. Different index pairs are distinct, so equal values may appear more than once.

Function

kSmallestPairSums(arr1: int[], arr2: int[], k: int) → int[]

Examples

Example 1

arr1 = [1,7,11]arr2 = [2,4,6]k = 4return = [3,5,7,9]

The first four sums come from (1,2), (1,4), (1,6), and (7,2).

Example 2

arr1 = [1,1,2]arr2 = [1,2]k = 5return = [2,2,3,3,3]

Different index pairs preserve duplicate sums.

Constraints

  • 1 <= arr1.length, arr2.length <= 100000.
  • Both arrays are sorted in nondecreasing order.
  • Every value is in [-10^9, 10^9].
  • 1 <= k <= arr1.length * arr2.length.
  • Every returned sum fits in a signed 32-bit integer.

More Google problems

See Google hiring insights
public int[] kSmallestPairSums(int[] arr1, int[] arr2, int k) {
    // Write your code here.
}
arr1[1,7,11]
arr2[2,4,6]
k4
expected[3,5,7,9]
Checking account…