DSA · Heap (Priority Queue) · #71

Find K Pairs with Smallest Sums

Module 60 · difficulty 3/5·⏱ 30:00starts on first keystroke

You are given two integer arrays `nums1` and `nums2` 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`. Implement `kSmallestPairs(nums1, nums2, k)` that returns the `k` pairs `(u1, v1), (u2, v2), ..., (uk, vk)` with the smallest sums. Each returned pair is `[u, v]`. If fewer than `k` pairs exist, return all of them. The order of the returned pairs does not matter (the grader normalises before comparing), but every returned pair must be among the `k` with the smallest sums.

Examples

nums1 = [1,7,11], nums2 = [2,4,6], k = 3 → [[1,2],[1,4],[1,6]] — The first 3 pairs by sum are (1,2)=3, (1,4)=5, (1,6)=7.
nums1 = [1,1,2], nums2 = [1,2,3], k = 2 → [[1,1],[1,1]] — Both 1's in nums1 pair with the first 1 in nums2, sum = 2.
nums1 = [1,2], nums2 = [3], k = 3 → [[1,3],[2,3]] — Only 2 pairs exist, so all of them are returned.

Constraints

· 1 <= nums1.length, nums2.length <= 10^5
· -10^9 <= nums1[i], nums2[i] <= 10^9
· nums1 and nums2 are sorted in non-decreasing order
· 1 <= k <= 10^4

Session phases

A · Clarify

B · Approach

C · Complexity

D · Edges

E · Code

F · Tradeoff

G · Score

Phase A — Clarify

Ask questions about input bounds, types, and edge constraints.

Ask the coach clarifying questions about the problem.

When you've covered this phase, advance to the next.