LeetCode 1046 · Heap / Priority Queue

Last Stone Weight, explained with a picture

Smashing the two heaviest rocks together.

EasyHeap / Priority Queue
▶ Watch it step by step

The problem

You have rocks with weights. Each turn, smash the two heaviest together: if they weigh the same both are destroyed, otherwise the lighter is destroyed and the heavier loses that much weight. Return the weight of the last rock left, or 0.

Input:  [2, 7, 4, 1, 8, 1]
Output: 1

Picture it

Picture a pile of rocks arranged so the heaviest is always on top: a max-heap. Each round we lift off the top two, smash them, and if anything is left over it goes back onto the pile, which re-sorts itself so the heaviest is on top again.

How to recognise it

  • Each step needs the largest item (here the two largest), and the result of the step goes back into the pile.
  • The pile changes after every step, so a sort done once at the start is not enough.
  • The process repeats until a simple stop condition: at most one item left.
  • "Always take the biggest" plus "put something back" is the textbook signature of a priority queue (a structure that always hands out its best item first). In practice that is a heap, a tree stored in a list with O(log n) push and pop.
  • The limits here are small (at most 30 stones of weight up to 1000), so the exercise is about the pattern, not about beating a time limit.

Start with brute force

Keep the stones in a list. Every round, sort it, remove the two heaviest, and add the leftover if they differ.

def last_stone_weight_brute(stones):
    s = list(stones)
    while len(s) > 1:
        s.sort()
        a = s.pop()          # heaviest
        b = s.pop()          # second heaviest
        if a != b:
            s.append(a - b)
    return s[0] if s else 0

Every round sorts up to n numbers, and there are up to n − 1 rounds, so time is O(n² log n) and extra space is O(n) for the copy. With n = 30 that is trivial. If the same rule were applied to 10^5 stones it would be about 10^5 rounds of sorting up to 10^5 numbers, around 10^11 steps, which is hopeless.

From brute force to the idea

  1. Find the waste. A full sort puts all n stones in order, but each round only needs the top two.
  2. Use a structure that serves the biggest. A heap gives the extreme item in O(log n) and accepts a new item in O(log n).
  3. Work around Python's min-heap. heapq always returns the smallest. Store each weight negated: the most negative number is the heaviest stone.
  4. Smash. Pop twice (negating back to get a and b, with a >= b). If a != b, push the leftover a - b, negated.
  5. Finish. When fewer than two stones remain, return the single one (negated back) or 0 if the heap is empty.

This is the key idea: a max-heap (negated min-heap) serves the two heaviest stones in O(log n) each.

The key idea

A max-heap hands over the two largest in O(log n) each; repeat until at most one rock remains.

Python solution

def last_stone_weight(stones):
    heap = [-s for s in stones]          # max-heap via negatives
    heapify(heap)
    while len(heap) > 1:
        a = -heappop(heap)                # heaviest
        b = -heappop(heap)                # second heaviest
        if a != b:
            heappush(heap, -(a - b))      # what’s left of the bigger rock
    return -heap[0] if heap else 0

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from heapq import heappush, heappop, heapify

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n² log n): up to n rounds, each with a sortO(n): the copied list
Max-heap (shown code)O(n log n): heapify is O(n), then at most n − 1 rounds of two pops and one push, each O(log n)O(n): the negated copy of the stones

Edge cases

  • One stone ([5]): the loop never runs and the answer is 5.
  • Two equal stones ([4, 4]): both are destroyed, the heap is empty, and the final guard returns 0.
  • All destroyed along the way ([1, 3, 2]): 3 and 2 leave 1, then 1 and 1 cancel, so the answer is 0.
  • Empty list: returns 0, because of the if heap else 0 guard. The problem promises at least one stone.
  • Input is not changed: the heap is built from a new list.
  • Imports: the shown code needs from heapq import heapify, heappush, heappop.

Common mistakes

  • Pushing a positive a - b onto the negated heap, which treats the leftover as the lightest stone.
  • Forgetting to negate after popping, so a and b are negative and the difference is wrong.
  • Dropping the if heap else 0 guard. When every stone cancels out, heap[0] raises IndexError.
  • Re-sorting the list each round "to keep it simple". It works at n = 30 but hides the point of the exercise.
Your turn: count the smashes

Use the same rules, but return how many smashes happen before at most one stone remains. For [2, 7, 4, 1, 8, 1] the answer is 4. Describe your approach, then write it if you like.

Compare with our answer

The heap loop is unchanged. Add a counter that goes up by one every time two stones are taken out. Nothing else matters, because each smash removes one or two stones.

from heapq import heapify, heappush, heappop

def count_smashes(stones):
    heap = [-s for s in stones]
    heapify(heap)
    smashes = 0
    while len(heap) > 1:
        a = -heappop(heap)
        b = -heappop(heap)
        smashes += 1
        if a != b:
            heappush(heap, -(a - b))
    return smashes

count_smashes([4, 4]) is 1 and count_smashes([1]) is 0. Time O(n log n), space O(n).

A strong answer mentions: keeping the same max-heap loop, counting once per pair taken out, and that the number of smashes is at most n − 1.

Check what stuck

1. A call centre always serves the longest-waiting customer next, and unfinished calls rejoin the queue with a new waiting time. Which structure fits best?

2. Why is the shown solution O(n log n) while the brute force is O(n² log n)?

3. A learner deletes the if heap else 0 guard and returns -heap[0] always. Which input now crashes?

Score 60% or more and the lesson is marked complete.