Find K Pairs with Smallest Sums

Problem

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 the first array and one element from the second array. Return the k pairs with the smallest sums.

Examples

The brute-force approach

Generate all pairs, sort by sum, return first k.

pairs = [(nums1[i]+nums2[j], i, j) for i in range(m) for j in range(n)]
pairs.sort()
return [[nums1[i], nums2[j]] for _, i, j in pairs[:k]]

O(mn log(mn)) — generates and sorts all pairs.

Spotting the pattern

This is a Heap / Priority Queue problem. The key question to ask yourself:

Why do you initialize the heap with (i, 0) for all i, and only push (i, j+1) after popping (i, j)? What would you miss by starting with fewer heap entries?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.