Last Stone Weight: Simulation on a Max-Heap

This one is a Easy-rated classic reported from Amazon, Google, Zillow interviews: "Last Stone Weight". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Top-K and Heaps pattern on sight. Part 2 of 11 in the Top-K and Heaps arc.

The Problem

Stones have weights; each turn, smash the two heaviest together. Equal weights destroy both; unequal leaves one stone of the difference. Return the last stone's weight, or 0. A warm-up whose real content is the Python max-heap idiom.

Input:  stones = [2, 7, 4, 1, 8, 1]
Output: 1
8 and 7 -> 1; 4 and 2 -> 2; 2 and 1 -> 1; 1 and 1 -> 0; one stone of 1 remains.

Recognizing the Top-K and Heaps Pattern

When a problem asks for the k largest, smallest, closest, or most frequent — or for repeated access to an extreme while data changes — a heap gives O(log n) insertion and O(1) access to the extreme. The signature trick: keep a bounded heap of size k with the opposite polarity (a min-heap to track the k largest), evicting the root on overflow. Python's heapq is a min-heap; negate values for max behavior.

Repeatedly take the current maximum from a shrinking collection — the mutation makes sorting once insufficient and a heap exactly right. Python has no built-in max-heap, so store negated values and negate on the way out; write the idiom without ceremony.

The Approach

Heapify the negated weights. While two stones remain, pop twice, push the negated difference when non-zero. Return the negation of the survivor, or 0 for an empty heap.

Each smash removes at least one stone, so at most n − 1 rounds of O(log n) heap work — a bound worth stating because simulation problems invite hand-waving.

Python Solution

import heapq


def last_stone_weight(stones: list[int]) -> int:
    """Weight of the final stone after all smashes, else 0."""
    heap = [-s for s in stones]        # negate: heapq is a min-heap
    heapq.heapify(heap)
    while len(heap) > 1:
        a = -heapq.heappop(heap)       # heaviest
        b = -heapq.heappop(heap)       # second heaviest
        if a != b:
            heapq.heappush(heap, -(a - b))
    return -heap[0] if heap else 0

Complexity

• Time: O(n log n) — heapify O(n), then up to n − 1 smashes at O(log n)
• Space: O(n) — the heap

Interview Tips and Follow-Ups

• Say why sorting once fails (the difference re-enters at an arbitrary position) — it justifies the heap in one sentence.
• The negation idiom generalizes: for max-heaps of tuples, negate the key field only. Practice it until it costs zero thought.
• Contrast with Last Stone Weight II — same story, but it becomes a subset-sum DP. Same costume, different pattern; recognizing that flip is the lesson.

More Top-K and Heaps problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.