Katkat
Back

Find k Smallest Pair Sums

AppleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently find the k-smallest pair sums from two sorted arrays using a heap-based approach to avoid exhaustive search.

Problem Statement

You are given two integer arrays nums1 and nums2, both sorted in non-decreasing order, and an integer k.

Define a pair (u, v) which consists of one element from nums1 and one element from nums2. Your task is to return a list of the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.

Function Signature

def kSmallestPairs(nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:

Constraints

  • 1 <= nums1.length, nums2.length <= 10^5
  • -10^9 <= nums1[i], nums2[i] <= 10^9
  • 1 <= k <= 10^4

Examples

Example 1: Input: nums1 = [1, 7, 11], nums2 = [2, 4, 6], k = 3 Output: [[1, 2], [1, 4], [1, 6]] Explanation: The first 3 pairs are the sequence of smallest sums [1+2, 1+4, 1+6].

Example 2: Input: nums1 = [1, 1, 2], nums2 = [1, 2, 3], k = 2 Output: [[1, 1], [1, 1]]

Edge Cases

  • k is larger than the total number of possible pairs.
  • Arrays contain duplicate values or negative numbers.

Hints

Hint 1

Since both arrays are sorted, the smallest possible sum must involve the smallest elements of both arrays.

Hint 2

Consider using a min-heap to keep track of the next smallest sum candidates, starting with pairs `(nums1[i], nums2[0])` for all `i`.

Hint 3

Every time you extract a pair `(nums1[i], nums2[j])` from the heap, the next potential candidate is `(nums1[i], nums2[j+1])`.

Follow-up questions

  • What is the time complexity of your solution in terms of k, N, and M (where N and M are the lengths of the arrays)?
  • How would you modify your algorithm if you needed to find the k-largest pair sums instead?
  • If the arrays were not sorted, how would that change your approach and the overall complexity?