LeetCode #373 Medium

Find K Pairs with Smallest Sums

Return up to k index pairs with the smallest sums from two sorted arrays.

arrayheapbest-first-search

02

Intuition

Generating and sorting every pair costs O(mn log(mn)), even when k is small. For a fixed index in nums1, pairing it with successive elements of sorted nums2 creates a sorted row of sums. The task is therefore to merge several sorted rows. A min-heap exposes the smallest current head and advances only the row that supplied it.

How to spot this pattern

Combining elements from sorted inputs often forms a monotone grid or sorted rows. If only the first k combinations are required, use best-first heap expansion instead of materializing the entire Cartesian product.

03

Approach

1

Seed only useful sorted rows

For each of the first min(k, len(nums1)) values, push its pair with nums2[0]. No later row can contribute before k earlier or equal row heads because nums1 is sorted.

2

Pop the globally smallest row head

The heap stores (sum, i, j). Remove its minimum, append [nums1[i], nums2[j]], and count it toward the requested output.

3

Advance within the selected row

If j + 1 exists, push (nums1[i] + nums2[j + 1], i, j + 1). Repeat until k pairs are returned or the heap empties because all possible pairs were used.

04

Solution

▶1class Solution:
▶2    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
▶3        if not nums1 or not nums2 or k == 0:
▶4            return []
▶5        heap = []
▶6        for i in range(min(k, len(nums1))):
▶7            heappush(heap, (nums1[i] + nums2[0], i, 0))
▶8        result = []
▶9        while heap and len(result) < k:
▶10            total, i, j = heappop(heap)
▶11            result.append([nums1[i], nums2[j]])
▶12            if j + 1 < len(nums2):
▶13                heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
▶14        return result

05

Common pitfalls

Seeding every possible pair

✗ Wrong

for i in range(len(nums1)):
    for j in range(len(nums2)):
        heappush(heap, (...))

✓ Right

for i in range(min(k, len(nums1))):
    heappush(heap, (nums1[i] + nums2[0], i, 0))

Materializing the Cartesian product defeats the output-sensitive advantage.

Advancing both indices

✗ Wrong

heappush(heap, (..., i + 1, j + 1))

✓ Right

heappush(heap, (..., i, j + 1))

Each heap entry belongs to one fixed nums1 row, whose next sum advances only in nums2.

Assuming k pairs always exist

✗ Wrong

while len(result) < k:

✓ Right

while heap and len(result) < k:

The Cartesian product may contain fewer than k pairs.

06

Edge cases

Either array is empty

Return an empty list before reading the first element of nums2.

k exceeds the number of pairs

The loop ends when the heap becomes empty and returns every available pair.

Duplicate values create equal sums

Index-based heap entries preserve each distinct pair occurrence.

07

Complexity

Time

O(k log min(k, m))

Space

O(min(k, m))

At most one frontier entry is stored for each seeded nums1 row.