Find K Pairs with Smallest Sums

MediumHeapheap

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given two integer arrays nums1 and nums2, each sorted in non-decreasing order, and an integer k. A pair (i, j) picks nums1[i] and nums2[j], and its sum is nums1[i] + nums2[j]. There are len(nums1) * len(nums2) pairs in total, counting pairs with equal values separately. Return the k pairs with the smallest sums as a list of [nums1[i], nums2[j]], ordered by **sum ascending, then by i ascending, then by j ascending**. This ordering fixes the output exactly even when sums or values repeat. k never exceeds the total number of pairs. Aim for O(k log min(k, len(nums1))) time.

Examples

Input: nums1 = [1,4,6], nums2 = [2,3,8], k = 4
Output: [[1,2],[1,3],[4,2],[4,3]]
Pair sums from smallest: 1+2=3, 1+3=4, 4+2=6, 4+3=7.
Input: nums1 = [1,1,3], nums2 = [1,2], k = 3
Output: [[1,1],[1,1],[1,2]]
Pairs (0,0) and (1,0) both sum to 2 and are ordered by i. Next, (0,1) and (1,1) both sum to 3; only (0,1) fits within k = 3.

Constraints

  • 1 <= nums1.length, nums2.length <= 1000
  • -10^9 <= nums1[i], nums2[j] <= 10^9
  • Both arrays are sorted in non-decreasing order.
  • 1 <= k <= min(10^4, nums1.length * nums2.length)

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More heap problems