nonme's blog

By nonme, history, 16 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.

Full text and comments »

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