My thoughts for the min_heap solution


  • 0
    H

    This problem is same as LC 378, so the solution is same. However, I guess most of us are confused by following method:
    if current min is (num1[m], num2[n]), we only insert (num1[m], num2[n+1]) into the heap, not (num1[m+1], num2[n]), unless n=0.

    We know we are extending the min_heap, but why in only 1 direction?
    In fact, if num1[m]+num2[n+1] > num1[m+1]+num2[n], then num1[m]+num2[n+1] > num1[m+1]+num2[n-1].
    If (num1[m+1],num2[n-1]) is already in min heap, then we are definitely safe, because (num1[m+1], num2[n]) will be inserted into queue before we pop out (num1[m], num2[n+1]).
    What if (num1[m+1],num2[n-1]) is not in queue? Well, then how about (num1[m+1],num2[n-2]), (num1[m+1],num2[n-3]), ... etc? One of them should be in the queue because (num1[m+1],num2[0]) is in the queue. And we know that we will extend 2 directions when n==0.

    This is some easy induction, but people may feel confused in the first and easily introduce duplicate pairs.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.