Last Stone Weight II - Leetcode 1049 - Python

[@iamsmitthakkar]

Just fyi: you don't have to have ceil(total // 2), it will work without ceil function as well Goes without saying - great explanation. Thank you for your videos.

[@CS_n00b]

This is too hard for a medium imo

[@iamnoob7593]

Got it thank you Neetcode.

[@Mr.Bombastic-tl5ic]

great explanation

[@Mr.Bombastic-tl5ic]

Nice question

[@rajshah9129]

when i saw this problem instantly max heap solution came in my mind removing top 2 element and adding their difference again in max heap and returning last remaining element from max heap? how can i come up with this like max heap solution will not work and intuition for your solution will work by reading question due to which part i can understand?

[@parthbhatia341]

I hate this question it tricks you into thinking it is a greedy problem.

[@saitejachebolu4798]

It can be done with meet in the middle algorithm

[@parashararamesh4252]

Would a greedy approach work? Have a Max heap and smash the top two and put the resultant back into the max heap. Can't think of a problem edge case where this fails

[@hamzaislam101]

Yeah I also thought of this

[@izumishark]

7,7,8,8,14,16

[@hamzaislam101]

@@izumishark got it 👍

[@m.kamalali]

Try this [31,26,33,21,40]

[@nikhil199029]

​@@m.kamalali yes it will work

[@theexplorer9012]

nice bra keep up

[@sheikhmkrifat7749]

My first thought was greedy, but it doesnt work , i dont know why.........

[@nikhil199029]

Why aren't we using heapsort?

[@albertd7658]

Because instead of smashing the largest/smallest stones in the array (Last Stone Weight I), we're smashing them to yield the minimum result. You could try to do heapsort on the first test case and it gives you a different result than 1 I believe.

[@tanishq2766]

No, in the second testcase it does though@@albertd7658

[@dhivakarsomasundaram21]

TypeError: '

[@yg1095]

You might not be returning dp[(i, total)] at the end of the function

[@dhivakarsomasundaram21]

@@yg1095 Nah man I copied and pasted as he posted here. inside the function of this variable dp[(i, total)] failed to evaluate the min(>/

[@vipsvips3213]

i love you

[@deadsippy]

this comment sent me for some reason 🤣🤣🤣

[@ary_21]

I have a doubt , i know it happens internally but still wanna know whats the time complexity of pushing any element x in a heap of size k?

[@ducthinh2412]

Pushing an element to a heap of size K is O(logK)

[@Alec____]

It's O(log K) because log K is the height of the balanced tree that represents the heap and worst case you have to move it up all the way from a leaf to the root (when you insert, you're inserting at the end of the array representing the heap, so it's a leaf)

[@vijayjagan8198]

can you cover mcm pattern

[@mithunverma225]

sir please create a playlist for these leetcode problems

[@supercarpro]

Did you look at his channel? He has multiple playlists. There's also a website, with all problems listed and courses he offers

[@huimingli9207]

1st, thanks for the daily upload

[@StellasAdi18]

That was tricky. Only genius like you can only come up in interview to realize it’s variation of 0/1 KP.

[@sherkrduotrg1978]

none of these solutions ever make sense to me 😔