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.
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?
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.
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)
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
This is too hard for a medium imo
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.
Got it thank you Neetcode.
great explanation
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?
I hate this question it tricks you into thinking it is a greedy problem.
It can be done with meet in the middle algorithm
My first thought was greedy, but it doesnt work , i dont know why.........
Nice question
i love you
this comment sent me for some reason 🤣🤣🤣
can you cover mcm pattern
nice bra keep up
Why aren't we using heapsort?
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.
No, in the second testcase it does though@@albertd7658
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?
Pushing an element to a heap of size K is O(logK)
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)
sir please create a playlist for these leetcode problems
Did you look at his channel? He has multiple playlists. There's also a website, with all problems listed and courses he offers
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
Yeah I also thought of this
7,7,8,8,14,16
@@izumishark got it 👍
Try this [31,26,33,21,40]
@@m.kamalali yes it will work
TypeError: '
You might not be returning dp[(i, total)] at the end of the function
@@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(>/
That was tricky. Only genius like you can only come up in interview to realize it’s variation of 0/1 KP.
none of these solutions ever make sense to me 😔
1st, thanks for the daily upload