Find K Pairs with Smallest Sums

Intuition

Because both arrays are sorted, the smallest possible sum is nums1[0] + nums2[0]. From any pair (i, j), the next candidates in increasing sum are (i+1, j) and (i, j+1), but exploring both explodes into duplicates. A cleaner frontier seeds the heap with the first column only: (i, 0) for each i. Popping the minimum yields the next smallest pair, and pushing (i, j+1) advances that row's pointer. This performs at most k pops, each touching one new candidate, so the heap never exceeds the number of seeded rows.

Algorithm walkthrough

1. 1If either array is empty, return an empty list.
2. 2Push (nums1[i], nums2[0]) for i from 0 to min(k, len(nums1)) - 1 into a min-heap keyed by the pair sum.
3. 3Pop the smallest pair and append (nums1[i], nums2[j]) to the answer.
4. 4If j + 1 is within nums2, push (nums1[i], nums2[j+1]) to extend that row.
5. 5Repeat until k pairs are collected or the heap empties.

Implementation

import heapq


class Solution:
    def kSmallestPairs(self, nums1: list[int], nums2: list[int], k: int) -> list[list[int]]:
        if not nums1 or not nums2:
            return []
        heap: list[tuple[int, int, int]] = []
        for i in range(min(k, len(nums1))):
            heapq.heappush(heap, (nums1[i] + nums2[0], i, 0))
        result: list[list[int]] = []
        while heap and len(result) < k:
            _, i, j = heapq.heappop(heap)
            result.append([nums1[i], nums2[j]])
            if j + 1 < len(nums2):
                heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
        return result