Maximum Subsequence Score - Leetcode 2542 - Python
Vložit
- čas přidán 27. 07. 2024
- Solving leetcode 2542 - Maximum Subsequence score, today's daily leetcode problem on may 23.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/maximum...
0:00 - Read the problem
1:30 - Drawing Explanation
9:45 - Coding Solution
leetcode 2542
#neetcode #leetcode #python
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.
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
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.
@@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.
@@user-fc9oh4kz5jes 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
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.
That was not medium unless one has seen before. Thanks for another amazing explanation!
I think it's important to clarify that the nums are guaranteed to not be negative
NGL, this hurt my brain a lil bit.
You and me, both.
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.
Good luck
good video as usual. Very different question when it comes to priority queue problems.
I mistaked this problem as DP problem on my first approach. Was surprised by the solution. Thanks for uploading.
Super helpful as always mr Neet 🙏thanks you
This approach is a pure magic...
Super smart solution which is also very easy to understand thanks to you.
Where are you nowadays? Why are you not posting to this channel anymore?
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...
your explanations are great
Very clear explanation. Thank you.
NGL I've watched this three times and I still do not get how this guarantees the score is maximized. 😥
wonderful explanation
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.
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.
@@milliepards96 Excellent explanation! I finally get it. Thank you!
which software you use for explaining the concept
Why do we add num2 to priority queue?
And not num1?
series on hard leetcode problem of Arrays, strings
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
no it does works a=(333333333333333333322222222222222225555555555555)
b=(111111111111111111111111111111111111111111111333333333333) for large number of duplicates
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!
Thank you very much brother. Thank you . Thank you. Thank you.
Nice, thanks. Should be hard, not medium !
Easier to initialize pairs like this:
pairs = list(zip(nums1, nums2))
pairs.sort(key = ...)
good video as usual
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.
You probably have important side-effects in your code. When it takes the answer from cache, it doesn't execute the side-effects.
Awesome!
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?
oh, it looks like it doesnt matter... im dumb
Hi. There is no point in creating a pairs object via a list comprehension.
Just put zip(nums1, nums2) into sorted().
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
Your explaination was really helpful, thanks!
thanks a lot!
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
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
U a Maximum Subsequence Score God
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.
Who could even create this problem. I find it so difficult to understand even watching the solution.
it is hard ig. :)
"medium"
After figuring out it is like medium..because this question has no strong COUNTER-HUMANITY logic behind this...