Maximum Subsequence Score - Leetcode 2542 - Python

[@swanv951]

Isn't it the case that at every iteration, when you include n2 (as the min from 2nd array subsequence) then you must include n1 (as the corresponding element from 1st array) in the running sum? You can't pop n1 from the minheap; you need to remove the other k-1 elements from the heap. I would think that you shouldn't add n1 to the heap in the first place and run the heap popping loop only till the heap becomes k-1 elements big.

[@mahimanzum]

exactly. The leetcode test cases are week. that's why that passed. You need to remove the smallest element from n1 first. the add the current value to the sum and calculate the answer in each iteration

[@NeetCodeIO]

Ah, that's a good catch. I'm surprised it passed on leetcode. In that case I think we could have two if-statements, one to check if len(heap) == k, if so, we pop. Then outside the if-statement, we push to the heap. Then another if-statement to check if len(heap) == k, if so, we update the result. So only a slight modification to fix the current solution, but it's a very subtle edge case. I guess thats why LC missed it.

[@JimmyLai-l1h]

@@mahimanzum Technically you're right. But I think it passed because NC's approach won't change the result, not due to weak test cases. If you pop the n1 you just add and still use its corresponding n2, yes it's against the rule, but since n1Sum would remain the same, and n2 is equal or smaller, it won't change res at all.

[@mahimanzum]

​​@@JimmyLai-l1hes you are correct. If both the value to be added in n1 sum is smaller and we are going from big to small values for n2, although we should use these values for this specific calculations, this will be smaller than the existing answer resulting is not Changing our preexisting answer and finally being not a problem

[@JimmyLai-l1h]

In NC's approach, it pops the new n1 only when it's the smallest. But since it's the smallest, if we pop the heap first and take that n1 & n2 pair, n1Sum would decrease and n2 would be equal or smaller, the score won't be greater than the previous result.

[@StellasAdi18]

That was not medium unless one has seen before. Thanks for another amazing explanation!

[@blatogh1277]

To anyone wants to have more easier understand on this question, it is recommend to write a slightly more complicate cases to solve this problem. Here is my analysis process. k = 4 num1: 2 1 6 4 2 7 3 1 8 3 num2: 8 7 6 5 4 4 3 2 2 1 default: num1: 2 1 6 4 num2: 8 7 6 5 -> (2,1,6,4) * 5 -> Heap: 1 2 4 6 round 1: num1: 2 1 6 4 2 num2: 8 7 6 5 4 (2 + who will be the maximum sum) * 4 ->1 out, 2 in -> Heap: 2 2 4 6 -> (2, 6, 4, 2) * 4 round 2: num1: 2 1 6 4 2 7 num2: 8 7 6 5 4 4 (7 + who will be the maximum sum) * 4 -> 2 out, 7 in -> Heap: 2 4 6 7 -> (7, 6, 4, 2) * 4 round 3: num1: 2 1 6 4 2 7 3 num2: 8 7 6 5 4 4 3 (3 + who will be the maximum sum) * 3 -> 2 out, 3 in -> Heap: 3 4 6 7 -> (3,4,6,7) * 3 round 4: num1: 2 1 6 4 2 7 3 1 num2: 8 7 6 5 4 4 3 2 (1 + who will be the maximum sum) * 2 -> 3out, 1 in -> Heap: 1 4 6 7 -> (1,4,6,7) * 2 round 5: num1: 2 1 6 4 2 7 3 1 8 num2: 8 7 6 5 4 4 3 2 2 (8 + who will be the maximum sum) * 2 -> 1 out, 8 in -> Heap: 4 6 7 8 -> (4,6,7,8) * 2 round 6: num1: 2 1 6 4 2 7 3 1 8 3 num2: 8 7 6 5 4 4 3 2 2 1 (3 + who will be the maximum sum) * 1 -> 4 out, 3 in -> Heap: 3 6 7 8 -> (3 6 7 8) * 1

[@ugookoh]

Your explaination was really helpful, thanks!

[@nithinsastrytellapuri291]

thanks a lot!

[@yueqiliao]

This approach is a pure magic...

[@TheElementFive]

I think it's important to clarify that the nums are guaranteed to not be negative

[@dadhx8]

I mistaked this problem as DP problem on my first approach. Was surprised by the solution. Thanks for uploading.

[@johnnychang3456]

Thank you for posting daily challenge videos. I am just starting to do daily challenges (4-day streak so far, lets go!) and your video is a life saver.

[@satishsingh8297]

Good luck

[@AnnoyingErrors41]

NGL, this hurt my brain a lil bit.

[@sanskartiwari2496]

You and me, both.

[@bhaikko4068]

If anyone still having issues or confusion after watching the video, here is a simplified version. This also includes why the above approach works After sorting the created pairs of nums1 and nums2 based on descending order of nums2, we iterate on each element of array of pair If we have not considered 'k' elements yet, we simply 'push to minHeap' and add 'currPair.num1' element to sumTillNow. However, if we have considered 'k' elements, we do the following and here's the intuition behind that. For current Pair, we know in currPair.nums2 will be the min element till now in nums2 which satisfies the later condition of our equation. This means we have to pick the same index element in nums1. So out of 'k' elements, we have picked 1 element and need to pick 'k-1' elements before this index. Since we need to maximize sum of 'k-1' elements, we use minHeap to remove minimum element from sum and thereby maintaining sum having maximum value since it will be consisting of 'k-1' max elements till current index.

[@metarus208]

Where are you nowadays? Why are you not posting to this channel anymore?

[@davidespinosa1910]

Nice, thanks. Should be hard, not medium ! Easier to initialize pairs like this: pairs = list(zip(nums1, nums2)) pairs.sort(key = ...)

[@Bhavisshyya]

I have a doubt , it can be case that you push n2 consecutive of n1 in heap but if that's the minimum and you pop it out of heap if size is greater . But in question you strictly need to consider the consecutive index.

[@milliepards96]

I think what you're asking about is a case where we push a number x from the nums1 list to the heap that is the smallest of those in the heap, which pushes the size of the heap over the edge (makes its size > k). In this case that number x would be popped from the heap immediatly, effectively making the heap the same as it was before we iterated over the current pair. In turn, the n1Sum would be exactly the same as before too. Now when we go to try and maximize res we are computing the score by multiplying n1Sum by a new multiplier (the n2 that came with x in the pair) that is guaranteed to be less than or equal to the previous multiplier. If you think about it, this product cannot possibly be larger than the previous one calculated. So even though the n1Sum isn't including x and we are using the multiplier that came with x, the resulting product will never be a solution that we return in the problem.

[@user-js7mq6jd2e]

@@milliepards96 Excellent explanation! I finally get it. Thank you!

[@Andyliu-q9r]

great great explanation but I think your code a little bit not match what you explained in the video. should it be to pop heap and update n1sum when Len(heap) ==k ? when len(heap)>k, what if the last added element is the smallest n1 among heap elements , you popped it but still use its corresponding n2 to multiply updated n1sum...

[@samreasor9743]

This is exactly what I was thinking. I know it’s been a while since you posted this, but could you please explain why this is passing on leet code lol. I completely understand the dilemma that you’re describing, and it’s bothering me that it passes. Are the test cases just garbage, or is there some mathematical reasoning

[@TheBackendDeveloper-b6t]

I am bit unsatisfied with the priority queue solution and think its probably wrong . Suppose you are popping from the minHeap , obviously its the min value , but a case may arise that the index you are currently at , the index of the minimum element which we are currently at and the element that is popped from the minHeap may have the same index in actual so thats a problem , because we are accounting the minimum at that point but we are excluding it in the sum and that is not acceptable . example : nums1 = [5,3,2,1] nums2 = [4,3,2,1] k = 2 so at the third index , we remove 2 from the minHeap of the nums1 array , but we are accounting the 2 from the nums2 . and that is where the case may be wrong . cause we need the indices of the subsequence , the order may be any for the subsequence but the indices must be same . And also i am confused how we are tracking the indices , cause everything seems to be out of track , cause there is no place of working with subsequence indices Can anyone explain me this part , how we are tackling the indices part and how we are going for the solution without considering the min and its index if the same index occurs for that element . Please help me , i didnt understood nicely and i am confused

[@chandratejabavandla]

In your example at the third index we first pop min from heap which is 3, and then include 2 for calculation, and take max of current result and previous result. Then 2 is pushed into heap

[@abhayphanse9509]

good video as usual. Very different question when it comes to priority queue problems.

[@MP-ny3ep]

Super smart solution which is also very easy to understand thanks to you.

[@list10001]

Very clear explanation. Thank you.

[@DonaldFranciszekTusk]

Hi. There is no point in creating a pairs object via a list comprehension. Just put zip(nums1, nums2) into sorted().

[@GameFlife]

Super helpful as always mr Neet 🙏thanks you

[@sakshamchhimwal322]

Thanks a lot, nice explanation!!

[@raghavendrac4710]

your explanations are great

[@karthikm.1804]

series on hard leetcode problem of Arrays, strings

[@edwardteach2]

U a Maximum Subsequence Score God

[@Raymond-Wu]

The only reason I got this was because there have been heap problems all week thus far. Not sure I would have thought of this type of solution otherwise!

[@jagrutitiwari2551]

Why do we add num2 to priority queue? And not num1?

[@vivekmit06]

Thank you very much brother. Thank you . Thank you. Thank you.

[@gilesbbb]

NGL I've watched this three times and I still do not get how this guarantees the score is maximized. 😥

[@divyansh2212]

wonderful explanation

[@XxRazcxX]

Would there be a case where you pop the n1 value that coincides with the n2? This one hurt my brain

[@samreasor9743]

This also bothers me. I was wondering if there’s some sort of mathematical reason, or if the test cases are just garbage

[@notgreen11]

instead of using a heap to find the k largest elements, couldn’t we maintain a mapping over nums1, first we map numbers to how often they appear, then we make a reverse mapping where the keys are frequencies (i.e. number appears twice) and the values are sets of numbers that appeared that many times. then when we want to find the largest sum after excluding up to n-k elements, we do n-k operations to update the mappings and then k operations to determine the largest numbers? would make the second half n complexity instead of nlogk, though still bounded by n. can’t try it right now though not at a computer

[@yaswanthkosuru]

no it does works a=(333333333333333333322222222222222225555555555555) b=(111111111111111111111111111111111111111111111333333333333) for large number of duplicates

[@j.sanjose3384]

Hi guys, I am honestly lost as to how the sorting actually works here. I understand that he's sorting based on a pair. Can anyone explain? I tried reviewing the video and looking at other sources but can't seem to wrap my head around it. Edit: I can't seem to understand how it affects the elements in num1.

[@praveenanand5689]

which software you use for explaining the concept

[@innoirvinge8431]

I thought subsequence means it has to be in the left to right order where you may or may not skip elements in between. How does sorting not break the subsequence ordering?

[@innoirvinge8431]

oh, it looks like it doesnt matter... im dumb

[@IK-xk7ex]

Awesome!

[@FlickeringFly]

good video as usual

[@Ankita-sd5gp]

can someone explain why we cant solve it with recursion & memoization, my recursion soln gives tle but on same code if i add memoization it gives wrong answer for few testcases, though recursively these same test-cases passes.

[@davidespinosa1910]

You probably have important side-effects in your code. When it takes the answer from cache, it doesn't execute the side-effects.

[@nikhilaradhya4088]

If someone can solve this problem in the first try, why would she want to work for others?

[@Sulerhy]

Who could even create this problem. I find it so difficult to understand even watching the solution.

[@manh9105]

The approach is not passing on leetcode now ....

[@erikshure360]

"medium"

[@blatogh1277]

After figuring out it is like medium..because this question has no strong COUNTER-HUMANITY logic behind this...

[@ceb-rj4qw]

it is hard ig. :)

[@RiazKhan-b6e]

Bad Explanation.

[@NeetCodeIO]

Any specifics? Otherwise this is a bad comment.

[@RiazKhan-b6e]

@@NeetCodeIO I am a big fan of you. But in this video you haven't explained clearly how heap is working to solve the problem. You are trying to shorten the video length. Please after explaining the problem, explain the algorithms clearly. In your all videos 95% time you have explained clearly. But in some cases you were trying to shorten the length so that these was hard to understand. Thank you!