Hello everyone! Today's LeetCode Daily problem is Find K Pairs with Smallest Sums.
Problem description
This problem is commonly solved with with priority queue. Here's a C++ solution for reference.
Solution with PQ
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.
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 is3(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.