EasyNeetCode150ArrayHeap (Priority Queue)
Last Stone Weight
Smash stones until one or none left.
Examples
Input
stones = [2,7,4,1,8,1]
Output
1
7-8=1, 4-2=2, 2-1=1, 1-1=0. Left: 1.
Constraints
- •
1 <= stones.length <= 30 - •
1 <= stones[i] <= 1000
Approaches
Sort descending, smash top 2.
CodeT: O(n^2 log n) | S: O(1)
def lastStoneWeight(stones):
while len(stones)>1:
stones.sort(reverse=True)
y=stones.pop(0); x=stones.pop(0)
if y!=x: stones.append(y-x)
return stones[0] if stones else 0Negate for max heap.
CodeT: O(n log n) | S: O(n)
import heapq
def lastStoneWeight(stones):
h=[-s for s in stones]; heapq.heapify(h)
while len(h)>1:
y=-heapq.heappop(h); x=-heapq.heappop(h)
if y!=x: heapq.heappush(h,-(y-x))
return -h[0] if h else 0Same approach.
CodeT: O(n log n) | S: O(n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Sort Each Time | O(n^2 log n) | O(1) | Sort descending, smash top 2. |
| Max Heap | O(n log n) | O(n) | Negate for max heap. |
| Max Heap Optimized | O(n log n) | O(n) | Same approach. |
Sort Each Time
T: O(n^2 log n)S: O(1)
Sort descending, smash top 2.
Max Heap
T: O(n log n)S: O(n)
Negate for max heap.
Max Heap Optimized
T: O(n log n)S: O(n)
Same approach.
Common Mistakes
Not handling empty result
Wrong comparison
Using min heap