Instead of working with flipped negative values, for the sake of clarity, I've implemented my code to convert these values each time. Python code: class Solution def lastStoneWeight(self, stones: List[int]) -> int: #implement a maxheap negativeHeap = [-x for x in stones] heapq.heapify(negativeHeap) while len(negativeHeap) > 1: largest = -1 * heappop(negativeHeap) largest2 = -1 * heappop(negativeHeap) if largest2 < largest: heappush(negativeHeap, -1 * (largest - largest2)) return -1 * negativeHeap[0] if negativeHeap else 0
Love your videos! Will probably comment on every video, trying to bing all of ur videos. and solve most of them using your amazing explanations and cleanest code solutions I've ever seen. Also joined your channel!
Popping from the heap is a O(logn) operation. By "get the maximum", Neetcode meant popping. The price of O(1) is for just looking at the maximum, but popping is more expensive.
Hey Neetcode! This is my last resort lol but can you please solve Basic Calculator 1? I've seen every resource on the net and I am yet to find one that really nails the concept. I love your videos and I am sure you will explain it beautifully!
more understandable for me def lastStoneWeight(self, stones: List[int]) -> int: stones = [-s for s in stones] heapq.heapify(stones) while len(stones) > 1: first, second = heapq.heappop(stones), heapq.heappop(stones) diff = - abs(first-second) heapq.heappush(stones, diff) return abs(stones[0])
Thank you for sharing this solution. I am working on my clarity of code. Here are what I learned from your code. 1. use a list initializer to store negative values. 2. use heapq.heapify , O(N), instead of in a for loop to heapq.heappush, O(NlogN) 3. pop the items out first, then compare them to decide whether to push or not. I compare them first, which results in redundant code. 4. last 2 lines are smart. append(0) in case the heap is empty. It's okay for me to use` return 0 if not heap else abs(stone[0])` though.
class Solution { public: static int lastStoneWeight(vector& stones) { // heapify -> O(n) make_heap(stones.begin(), stones.end()); while (stones.size() > 1){ // O(n) int first = stones.front(); pop_heap(stones.begin(), stones.end()); // log n stones.pop_back(); int second = stones.front(); pop_heap(stones.begin(), stones.end()); // log n stones.pop_back(); if (first != second){ // Note that the push_heap function assumes that the heap property is already satisfied for all elements except the last one. stones.push_back(first - second); push_heap(stones.begin(), stones.end()); // log n } } // Total time ==> n * (log n + log n + log n) === O (n log n) if (stones.size() == 1){ return stones[0]; } else{ return 0; } } };
Hey I've found out that checking case is redundant here because it will be the case every time as in minheap second elem always gonna be greater than first (or if equal then it will push 0 to the heap so we dont have to append an 0 at the end by ourselves)
you can also use sort() and grabbing the last 2 nums to get the difference if there is any. then once the while loop breaks out, you can either return stones[0] if len ==1. else just return 0.
At 11:56 when checking for edge case you wrote "stones.append(0)" I was wondering if this is allowed because we use a list function for a heap structure. I'm just making sure because this might be a loop hole since python is so laxed. If so wonderful python is awesome :D
It's ok because stones is still a list type, the list will just follow the heap structure when heapify if called - also, stones[0] will not change no matter how much you append to it.
abs() call is unnecessary because all stones have negative weight. So it is more clear to use "return -stones[0]" to be in sync with weights negation at start.
Thank you for the solution! I have a doubt though: Could you please explain why converting a list to a heap has O(n) time complexity ? Shouldn't it take O(nlogn) time?
This is because he converted the list into a heap using the heapify algorithm, which is O(n). Heapify builds the heap structure from bottom to top. If you build the heap structure from top to bottom, the time complexity will be O(nlogn),
//Just an 8-line code, but I used built-in functions more often in the code.// def last_stone_weight(arr): while len(arr)>1: arr.sort() a,b=arr.pop(),arr.pop() arr.append((a-b) if (a>b) else (b-a)) print(arr[0]) arr=[2,7,4,1,8,1] last_stone_weight(arr)
I think it is over complication to use heap in this case, there is max 30 stones in the list, so using list pop() and sort() methods is simpler and better solution.
Just negate the values coming out the heap and avoid the confusion. It's a single character (-). No need to multiply or use absolute value. first = -heapq.heappop(stones) second = -heapq.heappop(stones)
Great example! After running through the algorithm thoroughly, there is no need for the conditional "if" because the Max Heap will always maintain the top 2 highest values. def lastStoneWeight(self, stones): """ :type stones: List[int] :rtype: int """ stones = [-s for s in stones] heapq.heapify(stones) while len(stones) > 1: num1 = heapq.heappop(stones) num2 = heapq.heappop(stones) heapq.heappush(stones, num1 - num2) return abs(stones[0])
I have a question, since you are a big youtuber now, when we comment about how useful your videos are, do you still care ? I mean, does it make u happy ?
Great video! Just one criticism: please don't put hints (Priority Queue) in the video title. I like to try the problem myself first and then see how you do it. Thanks.
It turns out Python has max_heap implementation in heapq, it's just private and not documented for some reason. And I couldn't use _heappush_max, but can live without it :P def lastStoneWeight(self, stones: List[int]) -> int: # max heap is not a public member of heapq, rather a private one heapq._heapify_max(stones) while len(stones) > 1: a = heapq._heappop_max(stones) b = heapq._heappop_max(stones) if a != b: # a is NEVER less than b # there's no _heappush_max(), need to use heapify... stones.append(a - b) heapq._heapify_max(stones)
Instead of working with flipped negative values, for the sake of clarity, I've implemented my code to convert these values each time.
Python code:
class Solution
def lastStoneWeight(self, stones: List[int]) -> int:
#implement a maxheap
negativeHeap = [-x for x in stones]
heapq.heapify(negativeHeap)
while len(negativeHeap) > 1:
largest = -1 * heappop(negativeHeap)
largest2 = -1 * heappop(negativeHeap)
if largest2 < largest:
heappush(negativeHeap, -1 * (largest - largest2))
return -1 * negativeHeap[0] if negativeHeap else 0
No need to multiply by -1, just negate. i.e. "-x" instead of "-1 * x".
Still waitin' for the Last Stone Part 2 video. 💀 💀 💀
He said tomorrow. Be patient.
@@jayberry6557nah. Still waiting
Love your videos! Will probably comment on every video, trying to bing all of ur videos. and solve most of them using your amazing explanations and cleanest code solutions I've ever seen.
Also joined your channel!
Thank you so much, I really appreciate it!!!
Hi, Can you do Last Stone Weight II? Thanks
at 3:24 you say the time complexity to get the maximum is O(logn), but is it actually O(1)?
yes, the overall complexity should be O(n) ig
Popping from the heap is a O(logn) operation. By "get the maximum", Neetcode meant popping. The price of O(1) is for just looking at the maximum, but popping is more expensive.
Hey Neetcode! This is my last resort lol but can you please solve Basic Calculator 1? I've seen every resource on the net and I am yet to find one that really nails the concept. I love your videos and I am sure you will explain it beautifully!
more understandable for me
def lastStoneWeight(self, stones: List[int]) -> int:
stones = [-s for s in stones]
heapq.heapify(stones)
while len(stones) > 1:
first, second = heapq.heappop(stones), heapq.heappop(stones)
diff = - abs(first-second)
heapq.heappush(stones, diff)
return abs(stones[0])
exactly
@@bouzie8000 what is the point of the -abs? isn't that redundant because you are already doing return abs()
@@erickmercado1711 in the case there is a remaining diff, the negative helps it stay consistent when you push it back into the "max heap"
My interview prep starts here !!! Thanks a lot :)
Thank you for sharing this solution.
I am working on my clarity of code.
Here are what I learned from your code.
1. use a list initializer to store negative values.
2. use heapq.heapify , O(N), instead of in a for loop to heapq.heappush, O(NlogN)
3. pop the items out first, then compare them to decide whether to push or not. I compare them first, which results in redundant code.
4. last 2 lines are smart. append(0) in case the heap is empty. It's okay for me to use` return 0 if not heap else abs(stone[0])` though.
class Solution {
public:
static int lastStoneWeight(vector& stones) {
// heapify -> O(n)
make_heap(stones.begin(), stones.end());
while (stones.size() > 1){ // O(n)
int first = stones.front();
pop_heap(stones.begin(), stones.end()); // log n
stones.pop_back();
int second = stones.front();
pop_heap(stones.begin(), stones.end()); // log n
stones.pop_back();
if (first != second){
// Note that the push_heap function assumes that the heap property is already satisfied for all elements except the last one.
stones.push_back(first - second);
push_heap(stones.begin(), stones.end()); // log n
}
} // Total time ==> n * (log n + log n + log n) === O (n log n)
if (stones.size() == 1){
return stones[0];
}
else{
return 0;
}
}
};
My approach(wrong):
sort(stones.begin(), stones.end());
int sum1 = stones[0], sum2 = 0;
for(int i = 1; i < stones.size(); i++)
{
if(sum1 > sum2) sum2 += stones[i];
else sum1 += stones[i];
}
return abs(sum1 - sum2);
keep 2 variables sum1 & sum2
if(sum1 greater) add to sum2 else to sum1
Does the order of adding matters? Shouldn't this work?
Hey I've found out that checking case is redundant here because it will be the case every time as in minheap second elem always gonna be greater than first (or if equal then it will push 0 to the heap so we dont have to append an 0 at the end by ourselves)
you can also use sort() and grabbing the last 2 nums to get the difference if there is any. then once the while loop breaks out, you can either return stones[0] if len ==1. else just return 0.
True but it's slower. I tested it.
Thats O(n^2) no? nlogn * n
At 11:56 when checking for edge case you wrote "stones.append(0)" I was wondering if this is allowed because we use a list function for a heap structure. I'm just making sure because this might be a loop hole since python is so laxed. If so wonderful python is awesome :D
It's ok because stones is still a list type, the list will just follow the heap structure when heapify if called - also, stones[0] will not change no matter how much you append to it.
i think its bad coding..
abs() call is unnecessary because all stones have negative weight. So it is more clear to use "return -stones[0]" to be in sync with weights negation at start.
Thank you for the solution! I have a doubt though: Could you please explain why converting a list to a heap has O(n) time complexity ? Shouldn't it take O(nlogn) time?
This course will answer your question. th-cam.com/video/B7hVxCmfPtM/w-d-xo.html
because your going through the list stones in linear time one by one putting them in a heap structure.
This is because he converted the list into a heap using the heapify algorithm, which is O(n). Heapify builds the heap structure from bottom to top. If you build the heap structure from top to bottom, the time complexity will be O(nlogn),
Hi Neetcode, Thanks for all the amazing explanations. If possible, can u please make a video on Generalized Abbreviation problem
python's amazing... in JS, you need to write your own Heap first...
Awesome. Could you do one for Maximum Area of a Piece of Cake? Thanks!
You make it look so easy!!!
//Just an 8-line code, but I used built-in functions more often in the code.//
def last_stone_weight(arr):
while len(arr)>1:
arr.sort()
a,b=arr.pop(),arr.pop()
arr.append((a-b) if (a>b) else (b-a))
print(arr[0])
arr=[2,7,4,1,8,1]
last_stone_weight(arr)
Isn't it O(1) to pop a max from the heap?
Not popping because it has to reorganize the rest of the heap to correct for it. If it was just getting to top of the heap then yeah.
This was asked in NVIDIA interview
I think it is over complication to use heap in this case, there is max 30 stones in the list, so using list pop() and sort() methods is simpler and better solution.
Thanks!
Nice, Clean Code!
Just negate the values coming out the heap and avoid the confusion. It's a single character (-). No need to multiply or use absolute value.
first = -heapq.heappop(stones)
second = -heapq.heappop(stones)
Looking forward to Last Stone Weight II explanation
can you please explain the most optimized solution for this problem?
I love your voice mate!
Thank you !
thank you
Thanks man, liked
is the time complexity of the solution is O(n*3*log(n)) ?
Great example! After running through the algorithm thoroughly, there is no need for the conditional "if" because the Max Heap will always maintain the top 2 highest values.
def lastStoneWeight(self, stones):
"""
:type stones: List[int]
:rtype: int
"""
stones = [-s for s in stones]
heapq.heapify(stones)
while len(stones) > 1:
num1 = heapq.heappop(stones)
num2 = heapq.heappop(stones)
heapq.heappush(stones, num1 - num2)
return abs(stones[0])
Nice vid!
Awesome
the second will always be greater right ? i mean why is the if second> first even required?
They might be equal
Bro make a part 2 video please.
why don't you use abs(max(first, second)) and abs(min(first, second)) to get bigger_stone and smaller_stone respectively.?
because we already know which one is the bigger stone since we got it from the modified min heap
I have a question, since you are a big youtuber now, when we comment about how useful your videos are, do you still care ? I mean, does it make u happy ?
Great video! Just one criticism: please don't put hints (Priority Queue) in the video title. I like to try the problem myself first and then see how you do it. Thanks.
It turns out Python has max_heap implementation in heapq, it's just private and not documented for some reason. And I couldn't use _heappush_max, but can live without it :P
def lastStoneWeight(self, stones: List[int]) -> int:
# max heap is not a public member of heapq, rather a private one
heapq._heapify_max(stones)
while len(stones) > 1:
a = heapq._heappop_max(stones)
b = heapq._heappop_max(stones)
if a != b: # a is NEVER less than b
# there's no _heappush_max(), need to use heapify...
stones.append(a - b)
heapq._heapify_max(stones)
return stones[0] if stones else 0