Find K Pairs with Smallest Sums with M pointers?

#	User	Rating
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
8	ecnerwala	3494
9	Um_nik	3396
10	gamegame	3386

#	User	Contrib.
1	Um_nik	164
2	-is-this-fft-	162
3	maomao90	159
3	atcoder_official	159
5	cry	158
5	awoo	158
7	adamant	155
8	nor	154
9	TheScrasse	153
10	Dominater069	152

Hello everyone! Today's LeetCode Daily problem is Find K Pairs with Smallest Sums.

Problem description

You are given two integer arrays nums1 and nums2 sorted in ascending 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 (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.

Example 1:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:

Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [[1,3],[2,3]]
Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]

Constraints:

- 1 <= nums1.length, nums2.length <= 10^5
- -109 <= nums1[i], nums2[i] <= 10^9
- nums1 and nums2 both are sorted in ascending order.
- 1 <= k <= 10^4

This problem is commonly solved with with priority queue. Here's a C++ solution for reference.

Solution with PQ


class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<vector<int>> result;

        priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

        for (int i = 0; i < nums1.size(); ++i)
            pq.push({nums1[i] + nums2[0], 0}); // Sum and index of the second element

        while (k-- && !pq.empty()) {
            int sum = pq.top().first;
            int indx = pq.top().second;
            result.push_back({sum — nums2[indx], nums2[indx]});
            pq.pop();

            if (indx + 1 < nums2.size())
                pq.push({sum — nums2[indx] + nums2[indx + 1], indx + 1});
        }
        return result;
    }
};

Many users — and me in particular — initially tried to solve this problem with two pointers — and failed. But is there a way to solve this without priority queue anyway? Using three or more pointers? If not, why? Can it be proved?
Thanks for your attention in advance.

Comments (1)

Write comment?

polosatic

15 months ago, # |

Why do 2 pointers fail. I think they fail on something like this: nums1 = {3, 6, 9, 12, ...}, nums2 = {1, 4, 9, 16, 25, ...}, k = O(n). If you have 2 pointers i,j, your sum is 3i + j * j, and the algoritm thinks that next sum is 3(i + 1) + j * j or 3i + (j + 1) * (j + 1). But next sum can be equal to current sum. There are many exaplmes, e.g. 3 * 58 + 5 * 5 = 3 * 26 + 11 * 11. So we can't quickly find the sum using i and j.

Assume you use m pointers. I can't understand what it means if m > 2. I can only guess. I think it can be equivalent to solution with priority_queue with limited size. We need to remove maximal element from pq while pq.size() > m. We can remove nonmaximal elements, but it is less optimal. If you have another idea with m > 2, please explain.

→ Reply

nonme's blog