Maximum Subsequence Score - Leetcode 2542 - Python

  Рет қаралды 23,407

NeetCodeIO

NeetCodeIO

Күн бұрын

Пікірлер: 71
@swanv951
@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
@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
@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
@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
@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
@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
@StellasAdi18 Жыл бұрын
That was not medium unless one has seen before. Thanks for another amazing explanation!
@blatogh1277
@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
@ugookoh Жыл бұрын
Your explaination was really helpful, thanks!
@nithinsastrytellapuri291
@nithinsastrytellapuri291 11 ай бұрын
thanks a lot!
@TheElementFive
@TheElementFive Жыл бұрын
I think it's important to clarify that the nums are guaranteed to not be negative
@yueqiliao
@yueqiliao Жыл бұрын
This approach is a pure magic...
@johnnychang3456
@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
@satishsingh8297 Жыл бұрын
Good luck
@dadhx8
@dadhx8 Жыл бұрын
I mistaked this problem as DP problem on my first approach. Was surprised by the solution. Thanks for uploading.
@AnnoyingErrors41
@AnnoyingErrors41 Жыл бұрын
NGL, this hurt my brain a lil bit.
@sanskartiwari2496
@sanskartiwari2496 Жыл бұрын
You and me, both.
@bhaikko4068
@bhaikko4068 6 ай бұрын
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
@metarus208 Жыл бұрын
Where are you nowadays? Why are you not posting to this channel anymore?
@Bhavisshyya
@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
@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
@user-js7mq6jd2e 6 ай бұрын
@@milliepards96 Excellent explanation! I finally get it. Thank you!
@davidespinosa1910
@davidespinosa1910 9 ай бұрын
Nice, thanks. Should be hard, not medium ! Easier to initialize pairs like this: pairs = list(zip(nums1, nums2)) pairs.sort(key = ...)
@Andyliu-q9r
@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
@samreasor9743 3 ай бұрын
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
@abhayphanse9509
@abhayphanse9509 Жыл бұрын
good video as usual. Very different question when it comes to priority queue problems.
@MP-ny3ep
@MP-ny3ep Жыл бұрын
Super smart solution which is also very easy to understand thanks to you.
@TheBackendDeveloper-b6t
@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
@chandratejabavandla 10 ай бұрын
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
@DonaldFranciszekTusk
@DonaldFranciszekTusk 6 ай бұрын
Hi. There is no point in creating a pairs object via a list comprehension. Just put zip(nums1, nums2) into sorted().
@gilesbbb
@gilesbbb Жыл бұрын
NGL I've watched this three times and I still do not get how this guarantees the score is maximized. 😥
@GameFlife
@GameFlife Жыл бұрын
Super helpful as always mr Neet 🙏thanks you
@list10001
@list10001 5 ай бұрын
Very clear explanation. Thank you.
@karthikm.1804
@karthikm.1804 Жыл бұрын
series on hard leetcode problem of Arrays, strings
@Raymond-Wu
@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!
@sakshamchhimwal322
@sakshamchhimwal322 3 ай бұрын
Thanks a lot, nice explanation!!
@j.sanjose3384
@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.
@raghavendrac4710
@raghavendrac4710 Жыл бұрын
your explanations are great
@vivekmit06
@vivekmit06 Жыл бұрын
Thank you very much brother. Thank you . Thank you. Thank you.
@XxRazcxX
@XxRazcxX 3 ай бұрын
Would there be a case where you pop the n1 value that coincides with the n2? This one hurt my brain
@samreasor9743
@samreasor9743 3 ай бұрын
This also bothers me. I was wondering if there’s some sort of mathematical reason, or if the test cases are just garbage
@notgreen11
@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
@yaswanthkosuru Жыл бұрын
no it does works a=(333333333333333333322222222222222225555555555555) b=(111111111111111111111111111111111111111111111333333333333) for large number of duplicates
@yenosibinamakanjuola9249
@yenosibinamakanjuola9249 9 күн бұрын
I saw the question and read it and gave upp
@edwardteach2
@edwardteach2 5 ай бұрын
U a Maximum Subsequence Score God
@jagrutitiwari2551
@jagrutitiwari2551 6 ай бұрын
Why do we add num2 to priority queue? And not num1?
@divyansh2212
@divyansh2212 Жыл бұрын
wonderful explanation
@innoirvinge8431
@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
@innoirvinge8431 Жыл бұрын
oh, it looks like it doesnt matter... im dumb
@praveenanand5689
@praveenanand5689 Жыл бұрын
which software you use for explaining the concept
@Ankita-sd5gp
@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
@davidespinosa1910 9 ай бұрын
You probably have important side-effects in your code. When it takes the answer from cache, it doesn't execute the side-effects.
@janakiramankirthivasan5955
@janakiramankirthivasan5955 2 күн бұрын
I hate this problem and probably need to rewatch the solution
@Sulerhy
@Sulerhy 7 ай бұрын
Who could even create this problem. I find it so difficult to understand even watching the solution.
@nikhilaradhya4088
@nikhilaradhya4088 Ай бұрын
If someone can solve this problem in the first try, why would she want to work for others?
@FlickeringFly
@FlickeringFly Жыл бұрын
good video as usual
@IK-xk7ex
@IK-xk7ex Жыл бұрын
Awesome!
@manh9105
@manh9105 2 ай бұрын
The approach is not passing on leetcode now ....
@erikshure360
@erikshure360 Жыл бұрын
"medium"
@blatogh1277
@blatogh1277 Жыл бұрын
After figuring out it is like medium..because this question has no strong COUNTER-HUMANITY logic behind this...
@ceb-rj4qw
@ceb-rj4qw Жыл бұрын
it is hard ig. :)
@RiazKhan-b6e
@RiazKhan-b6e Ай бұрын
Bad Explanation.
@NeetCodeIO
@NeetCodeIO Ай бұрын
Any specifics? Otherwise this is a bad comment.
@RiazKhan-b6e
@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!
New 21 Game - Leetcode 837 - Python
19:03
NeetCodeIO
Рет қаралды 13 М.
Making an Algorithm Faster
30:08
NeetCodeIO
Рет қаралды 147 М.
Молодой боец приземлил легенду!
01:02
МИНУС БАЛЛ
Рет қаралды 1,9 МЛН
The Singing Challenge #joker #Harriet Quinn
00:35
佐助与鸣人
Рет қаралды 44 МЛН
Hoodie gets wicked makeover! 😲
00:47
Justin Flom
Рет қаралды 133 МЛН
THE BIG WIN PROMOTION
1:32
Timely Talks
Рет қаралды 969
Leetcode  2542  Maximum Subsequence Score
30:14
Java Coding Insight Interview Preparation
Рет қаралды 132
Maximum Matrix Sum - Leetcode 1975 - Python
16:07
NeetCodeIO
Рет қаралды 553
Coding Unbreakable Encryption in C | One-Time Pad
17:42
HirschDaniel
Рет қаралды 4,3 М.
Python Data Classes Are AMAZING! Here's Why
16:11
Tech With Tim
Рет қаралды 85 М.
2542. Maximum Subsequence Score | LeetCode Daily Challenge
21:31
Evaluate Division - Leetcode 399 - Python
17:37
NeetCodeIO
Рет қаралды 32 М.
Stone Game II - Leetcode 1140 - Python
18:40
NeetCodeIO
Рет қаралды 23 М.
Premature Optimization
12:39
CodeAesthetic
Рет қаралды 834 М.
Dynamic Programming isn't too hard. You just don't know what it is.
22:31
DecodingIntuition
Рет қаралды 197 М.
Молодой боец приземлил легенду!
01:02
МИНУС БАЛЛ
Рет қаралды 1,9 МЛН