LeetCode Top Interview 150 P373 Find K Pairs with Smallest Sums

---

Timeline

timeline

2025-12-08

init

heap

---

Problem:

P373 Find the smallest sum ofKpairs 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 using a heap is to first put all {nums1[0], nums2[j]} into the heap (0 <= j <= nums2.size()), then remove the pair {i, j} with the smallest sum from the heap. When j is fixed, among the larger values, {i+1, j} is the smallest.

Why can j remain unchanged? Because the advancement of j (i.e., j+1) has already been added to the heap during initialization ({nums1[0], nums2[j]}).

Example 1’snums1 = [1, 7, 11]，nums2 = [2, 4, 6]. We calculate the sum of each pair and obtain 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}$$

Sincenums2is 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$ isnums1(length) According to the heap approach of merging K sorted linked lists from P23:

1. Add the first number $M_{i,0}$ of each row of the matrix and its position $(i, 0)$ to the min-heap.
2. Loop $k$ times.
3. Each loop, pop the top of the heap, take the top $M*{i,j}$ corresponding number pair into the answer, take 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;
        }
};