nonme's blog

Find K Pairs with Smallest Sums with M pointers?
By nonme, history, 18 months ago, In English

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.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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