Interview Classic 150 Questions P373 Find K Pairs with Smallest Sums

---

Timeline

Timeline

2025-12-08

init

heap

---

Problem:

P373 Find the smallest sumKpairs of numbers

https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/description/?envType=study-plan-v2&envId=top-interview-150

This problem cannot use two pointers because it is not linear. The core of solving it with a heap is to first put all {nums1[0], nums2[j]} into the heap (0 <= j <= nums2.size()), then pop the pair {i,j} with the smallest sum from the heap. With j unchanged, among the values greater than it, {i+1, j} is the smallest.

Then why can we keep j unchanged? Because the advancement of j (i.e., j+1) has already been fully added to the heap during initialization ({num1[0], nums2[j]}).

of Example 1nums1 = [1, 7, 11]，nums2 = [2, 4, 6]We compute the sum of each pair, and we can get a matrix $M$, where $M_{i,j} = nums1[i] + nums2[j]$.

$$M = \begin{bmatrix} 3 & 5 & 7 \\ 9 & 11 & 13 \\ 13 & 15 & 17 \end{bmatrix}$$

Sincenums2are increasing, so each row of the matrix is increasing. The problem is equivalent to: merge $n$ sorted lists and find the first $k$ smallest elements. (where $n$ isnums1the length of) According to the heap approach of P23 Merge K Sorted Lists:

1. Add the first number of each row of the matrix $M_{i,0}$ and its position $(i, 0)$ to the min-heap.
2. Loop $k$ times.
3. Each iteration, pop the heap top, and the heap top $M*{i,j}$'s corresponding pair is added to the answer, and the element to the right of the heap top $M*{i,j+1}$ and its position $(i, j+1)$ into the heap.

#include <vector>
#include <queue>
#include <utility>
#include <array>
using std::vector;
using std::pair;
using std::priority_queue;
using std::array;

class Solution {
    public:
        vector<vector<int> > kSmallestPairs(vector<int> &nums1,
                                            vector<int> &nums2, int k)
        {
                vector<vector<int> > res;
                if (nums1.empty() || nums2.empty() || k == 0)
                        return res;

                auto cmp = [&](const array<int, 2> &a, const array<int, 2> &b) {
                        return nums1[a[0]] + nums2[a[1]] >
                               nums1[b[0]] + nums2[b[1]];
                };
                priority_queue<array<int, 2>, vector<array<int, 2> >,
                               decltype(cmp)>
                        pq(cmp);


                for (int i = 0; i < nums1.size() && i < k; i++) {
                        pq.push({ i, 0 });
                }

                while (k-- && !pq.empty()) {
                        auto [i, j] = pq.top();
                        pq.pop();
                        res.push_back({ nums1[i], nums2[j] });

                        if (j + 1 < nums2.size()) {
                                pq.push({ i, j+1 });
                        }
                }

                return res;
        }
};