LeetEye LeetEye
Hard Heap / Priority Queue ~5 min

Last Stone Weight

heap last-stone-weight

Problem

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:
- If x == y, both stones are destroyed.
- If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

Examples

Example 1
Input: stones = [2,7,4,1,8,1]
Output: 1
Key Insight

Max-heap gives O(log n) access to largest elements.

Max-heap for 'heaviest two' access. Pop two, push difference if nonzero. Return last remaining or 0.

How to Approach This Problem

Pattern Recognition: When you see keywords like last stone weight heap, think Heap / Priority Queue.

Step-by-Step Reasoning

1 We use a heap because:
Answer: We need quick access to maximum elements
Extracting two max elements repeatedly = heap's strength.
2 We need:
Answer: Max-heap
We want the two heaviest. Max-heap gives max at root.
3 Python's heapq is a min-heap. To simulate max-heap:
Answer: Negate all values
Negating turns max into min. pop gives -max = actual max.
4 After smashing stones x and y (x <= y):
Answer: Push y-x only if y-x > 0
If y == x, both destroyed (nothing to push). Otherwise push remainder.
5 We stop when:
Answer: Heap has <= 1 element
With 0 stones, answer is 0. With 1 stone, answer is its weight.
6 Final answer is:
Answer: Heap root if heap has 1 element, else 0
Either one stone left or no stones left.

Solution

import heapq

def lastStoneWeight(stones: List[int]) -> int:
    # Use negative values for max-heap
    heap = [-s for s in stones]
    heapq.heapify(heap)
    
    while len(heap) > 1:
        y = -heapq.heappop(heap)  # Largest
        x = -heapq.heappop(heap)  # Second largest
        
        if y != x:
            heapq.heappush(heap, -(y - x))
    
    return -heap[0] if heap else 0

Complexity Analysis

Time O(n log n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Heap / Priority Queue problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye