0% completed
There exists an O(KLogK) solution using a heap, but requires some non-obvious in...
Will
Jun 1, 2022
There exists an O(KLogK) solution using a heap, but requires some non-obvious insight to come up with it. See Leetcode question 373.
1
0
Comments
Will 3 years ago
If interested, this particular comment is quite useful in understanding the intuition behind this O(KlogK) optimal solution (link: [https://leetcode.com/problems/find-k-pairs-with-smallest-sums/discuss/84607/Clean-16ms-C++-O](https://leetcode.com/problems/find-k-pairs-...
Will 3 years ago
Quoted from Fentoyal's LC comment (from link above), altered slightly to match this question: "Suppose you are at pair 0,0 (index 0 and index 0, not value), which is the current maximum. Then you know the only two possible followers (immediate smaller ones) are indices ...
Will 3 years ago
Or this from another comment:
L1 = [16, 11, 7, 1] L2 = [15, 10, 9, 2]
"It is hard for me to understand at the beginning, but I finally came up with an idea to view this question, hope it can help you!
It is actually the same as how we merge k sorted list, in this que...
On this page