DSA problem
Find K Pairs with Smallest Sums
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. Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.
The brute force approach generates every pair (m * n total), sorts them by sum, and takes the first k. That costs O(m * n log(m * n)) time and O(m * n) space — far too expensive when m and n are large but k is small.
The key observation is that both input arrays are already sorted. For any fixed i, the sums nums1[i] + nums2[j] are sorted as j increases. So if we have already used the pair (i, j), the next best pair involving index i on the left is exactly (i, j + 1). This is a classic k-way merge: we have min(k, m) sorted streams, one per row i, and we want the global smallest k sums across all streams.
The optimal approach uses a min-heap. Seed the heap with the pair (nums1[i] + nums2[0], i, 0) for i in 0..min(k, m) - 1 — that's the smallest pair from each candidate row. Then repeat k times: pop the minimum, record the pair, and push the next candidate (nums1[i] + nums2[j + 1], i, j + 1) if j + 1 < n. The heap holds at most min(k, m) entries, so each push/pop costs O(log k), and the total work is O(k log k) time with O(k) space — independent of how large m and n become.
Examples
nums1 = [1,7,11], nums2 = [2,4,6], k = 3[[1,2],[1,4],[1,6]]nums1 = [1,1,2], nums2 = [1,2,3], k = 2[[1,1],[1,1]]nums1 = [1,2], nums2 = [3], k = 3[[1,3],[2,3]]Constraints
- 1 <= nums1.length, nums2.length <= 10^5
- -10^9 <= nums1[i], nums2[i] <= 10^9
- nums1 and nums2 both are sorted in non-decreasing order.
- 1 <= k <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.