Why it works
- nums2 is sorted, so each row of sums grows to the right. The pairs are k sorted lists, one per row, and the next smallest sum is always the first unused pair of some row.
- The heap holds exactly that first unused pair of every row, so its top is the next smallest sum. After a pop, the row moves on by one pair.
- The run stops after k pops: pairs further right in each row are never built, like the 9s here.
Complexity
Time O(n + k log n), where n is the length of nums1: a heap of one pair per row, then k pops and at most k pushes. Memory O(n + k) for the heap and the answer.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗