Last Stone Weight: Max Heap Pattern

You have a collection of stones, each with a positive integer weight. On each turn you pick the two heaviest stones and smash them together. If they have equal weight, both are destroyed. If they differ, the lighter one is destroyed and the heavier one loses weight equal to the lighter one. You repeat until at most one stone remains. Return its weight, or 0 if no stones are left.

This is LeetCode 1046: Last Stone Weight, and it is one of the cleanest introductions to the max heap data structure. The problem reads like a game simulation, but the real lesson is learning when and how to use a heap to repeatedly extract maximums efficiently.

Why this problem matters

Sorting the array and picking the top two works for one round, but you need to re-sort after inserting the remainder. Sorting every round is O(n log n) per turn, and with up to n turns that becomes O(n^2 log n). That is far more work than necessary.

A max heap gives you O(log n) insertion and O(log n) extraction of the maximum. Each round requires two extractions and at most one insertion, all O(log n) operations. Over n rounds, total time is O(n log n), which is as good as a single sort.

This pattern, repeatedly extracting the largest (or smallest) element and reinserting a modified value, is the textbook use case for a heap. You will see the same structure in problems like Kth Largest Element, task scheduling, merge k sorted lists, and Huffman coding.

The approach

The algorithm is a direct simulation powered by a max heap:

1. Push all stone weights into a max heap.
2. While the heap has more than one stone, pop the two largest.
3. If they are not equal, push the difference back into the heap.
4. When the loop ends, return the last stone (or 0 if the heap is empty).

Python's heapq module implements a min-heap, so you negate the values to simulate a max heap. Push -weight instead of weight, and negate again when you pop.

The solution

import heapq

def last_stone_weight(stones: list[int]) -> int:
    heap = [-s for s in stones]
    heapq.heapify(heap)

    while len(heap) > 1:
        first = -heapq.heappop(heap)
        second = -heapq.heappop(heap)
        if first != second:
            heapq.heappush(heap, -(first - second))

    return -heap[0] if heap else 0

Let's walk through what each piece does.

The first two lines convert the input into a max heap. Since Python only provides a min-heap, you negate every value so the largest stone has the most negative value and sits at the top. heapify arranges the list into heap order in O(n) time.

Inside the loop, you pop twice to get the two heaviest stones. You negate when popping to recover the original positive weights. If the stones differ, you push the difference (negated) back into the heap. If they are equal, neither goes back, which is equivalent to both being destroyed.

The loop ends when zero or one stone remains. If the heap is non-empty, you return the last stone's weight (negated back to positive). If the heap is empty, all stones were destroyed and you return 0.

Visual walkthrough

Let's trace through stones = [2, 7, 4, 1, 8, 1] step by step. At each round, the two heaviest stones are popped, smashed, and the remainder (if any) is pushed back.

Notice that each round reduces the heap size by one (when stones differ) or by two (when they are equal). After four rounds, only one stone with weight 1 remains.

Complexity analysis

Time is O(n log n). Building the heap is O(n). Each of the at most n rounds does two pops and at most one push, each O(log n). With at most n rounds, the total is O(n log n).

Space is O(n) for the heap. In Python, heapify operates in place on the list, so no extra allocation is needed beyond the input. If you are working with an immutable input, you need an O(n) copy.

The building blocks

1. Max heap extraction loop

The pattern of repeatedly extracting the maximum element from a heap and processing it:

while len(heap) > 1:
    largest = -heapq.heappop(heap)
    second = -heapq.heappop(heap)
    if largest != second:
        heapq.heappush(heap, -(largest - second))

This "pop two, process, maybe push one back" structure appears whenever you need to repeatedly combine or compare the largest elements. You see it in Huffman coding (pop two smallest, combine, push result), merge k sorted lists (pop smallest, advance, push next), and task scheduling (pop highest priority, process, re-enqueue). The heap guarantees you always work with the extremes in O(log n) time instead of scanning the entire collection.

2. Min-heap as max-heap via negation

The pattern of negating values to turn Python's min-heap into a max-heap:

heap = [-x for x in values]
heapq.heapify(heap)
largest = -heapq.heappop(heap)
heapq.heappush(heap, -new_value)

This is the standard workaround for Python's lack of a built-in max-heap. You negate on insert and negate on extract. The key is consistency: every value in the heap must be negated, and you must remember to negate back when reading. This two-line pattern shows up in virtually every Python heap problem, from Kth Largest Element to Top K Frequent Elements to median finding.

Edge cases

Before submitting, think through these scenarios:

• Single stone: the heap has one element, the loop never runs, and you return that stone's weight.
• Two equal stones: pop both, difference is 0, nothing is pushed back. Heap is empty. Return 0.
• Two different stones: pop both, push the difference. Return it.
• All stones equal: pairs cancel out. If the count is even, return 0. If odd, return the stone weight.
• Very large weights: stone weights can be up to 1000. With at most 30 stones, no overflow concerns in Python.
• Already sorted input: the heap handles any input order. No special handling needed.

From understanding to recall

You have seen how a max heap turns the Last Stone Weight simulation into an efficient algorithm: heapify, pop two, smash, push remainder, repeat. The logic is clean and the code is short.

But writing it correctly under pressure requires remembering the negation trick, the loop termination condition, and the edge case where the heap ends up empty. These are not conceptual gaps. They are recall gaps, the kind that cost time during interviews when you are rederiving details you have seen before.

Spaced repetition closes the gap. You practice the heap extraction loop and the negation pattern from memory at increasing intervals. After a few rounds, the template is automatic. You see "repeatedly pick the largest" in a problem statement, and the heap code flows out without hesitation.

Related posts

• Kth Largest Element - Uses a min-heap of size k to find the kth largest, the complementary heap pattern
• Top K Frequent Elements - Combines frequency counting with a heap to extract the top k, another core heap application
• Koko Eating Bananas - A different flavor of simulation problem where binary search replaces the heap

CodeBricks breaks Last Stone Weight into its max heap extraction loop and negation pattern building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a heap problem shows up in your interview, you do not think about it. You just write it.