Last Stone Weight: the heap's simplest showcase

Pick the two heaviest stones, smash them together, put the remainder back. Repeat until at most one stone survives. That's the whole problem — and it reads like a textbook definition of "when to use a heap." Which makes it a good first real exercise in the heap-priority-queue series: not because it's hard, but because it forces you to articulate exactly why a heap is the right tool and what the alternatives cost.

What the constraints actually say

1 <= stones.length <= 30. Thirty stones. This is small enough that a loop of O(n²) passes in under a microsecond. The constraint is not forcing you toward an optimal solution for performance reasons — at n=30, even a bubble-sort-based simulation is instant. What the constraint does tell you is that sorting the entire list each round is not catastrophic here. It works. The question is whether it's the cleaner approach.

1 <= stones[i] <= 1000. All weights are positive. This matters for one subtle reason: when you compute y - x after a smash, the result is guaranteed to be non-negative, so you never insert a zero or negative weight back into the collection. That keeps the heap invariant clean — every element sitting in the heap is a valid remaining stone weight.

The implicit constraint nobody writes down: you need the two maximum elements repeatedly, and after each extraction the collection changes. That's the shape of a heap problem. Not "find the max once" (that's just max()), not "sort once and process in order" (that's a stack or two-pointer), but "maintain dynamic access to the max as elements are added and removed."

Brute force: sort every round

The straightforward simulation: before each smash, sort the list, pull the last two elements, compute the remainder, append it if nonzero, repeat.

class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        while len(stones) > 1:
            stones.sort()
            y = stones.pop()  # heaviest
            x = stones.pop()  # second heaviest
            if y != x:
                stones.append(y - x)
        return stones[0] if stones else 0

public class Solution {
    public int LastStoneWeight(int[] stones) {
        var list = new List<int>(stones);
        while (list.Count > 1) {
            list.Sort();
            int y = list[list.Count - 1];
            int x = list[list.Count - 2];
            list.RemoveAt(list.Count - 1);
            list.RemoveAt(list.Count - 1);
            if (y != x) list.Add(y - x);
        }
        return list.Count > 0 ? list[0] : 0;
    }
}

Time: O(n² log n). Each iteration sorts in O(n log n), and you can have up to n iterations (each smash reduces the stone count by at least one, occasionally by two). Space: O(1) extra, since you're sorting in-place.

At n=30 this is completely fine. I'd actually write this first in an interview to get something correct on the board quickly, then explain why the heap version is cleaner if the constraints grew. The sorting approach has one nice property: it requires zero heap knowledge and is obviously correct.

The problem with it at scale is the redundancy. You're sorting the entire remaining list to find two elements. Most of that sorted order is information you immediately discard — after the smash, you need the new maximum, not a fully ordered list.

Max-heap approach: O(n log n)

A max-heap gives you the largest element in O(1) peek and removes it in O(log n). Building one from n elements costs O(n). The loop runs at most n times (each smash removes at least one stone), each iteration does two O(log n) extractions and at most one O(log n) insertion. Total: O(n log n).

Python's heapq is a min-heap. The standard trick is to negate the values before inserting, then negate again on extraction.

import heapq
 
class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        heap = [-s for s in stones]
        heapq.heapify(heap)
 
        while len(heap) > 1:
            y = -heapq.heappop(heap)
            x = -heapq.heappop(heap)
            if y != x:
                heapq.heappush(heap, -(y - x))
 
        return -heap[0] if heap else 0

C# has PriorityQueue<TElement, TPriority> (available since .NET 6). It's a min-heap over the priority value. Pass -stone as the priority to flip the ordering.

public class Solution {
    public int LastStoneWeight(int[] stones) {
        var pq = new PriorityQueue<int, int>();
        foreach (int s in stones)
            pq.Enqueue(s, -s);
 
        while (pq.Count > 1) {
            int y = pq.Dequeue();
            int x = pq.Dequeue();
            if (y != x)
                pq.Enqueue(y - x, -(y - x));
        }
 
        return pq.Count > 0 ? pq.Peek() : 0;
    }
}

Space: O(n) for the heap. You trade O(n) space for the reduction from O(n² log n) to O(n log n). At n=30 this trade is irrelevant; at n=10⁶ it's the difference between fast and workable.

Step-by-step trace: [2, 7, 4, 1, 8, 1]

The expected output is 1. Let me walk through the heap version:

Round 1: extract 8 and 7. 8 - 7 = 1. Push 1 back. Heap becomes [4, 2, 1, 1, 1].

Round 2: extract 4 and 2. 4 - 2 = 2. Push 2. Heap: [2, 1, 1, 1].

Round 3: extract 2 and 1. 2 - 1 = 1. Push 1. Heap: [1, 1, 1].

Round 4: extract 1 and 1. Equal, both destroyed. Nothing pushed. Heap: [1].

One element remains. Return 1. Matches the expected output.

Edge cases

Single stone (stones = [1]): the while len > 1 condition is false immediately. The heap has one element; return it. Nothing to worry about.

Two equal stones (stones = [3, 3]): both destroyed in one round. Heap is empty after the pop. The final return heap[0] if heap else 0 returns 0. This is the only case where the answer is 0.

All equal, even count (stones = [2, 2, 2, 2]): pairs cancel each other. Heap empties completely. Return 0.

All equal, odd count (stones = [2, 2, 2]): two cancel, one remains. Return 2. The parity of the initial count determines whether you get 0 or the original weight.

Weights at the boundary (stones[i] = 1000): the maximum difference is 999. No overflow risk in Python (arbitrary precision integers). In C#, the values are int — maximum difference 999, well within int range.

The comparison

At n=30, both pass comfortably. If the problem had 1 <= stones.length <= 10^5, the sorting approach would TLE — each round is O(n log n) and you might have O(n) rounds. The heap version handles that cleanly.

I'd ship the heap version in production code because it expresses the intent directly: "I need repeated access to the maximum." The sort-each-round version is a workaround that happens to work.

The mental model: "dynamic max access"

This problem is a canonical example of what I call the dynamic max access pattern: you have a collection where you repeatedly need the maximum (or minimum), and the collection changes between queries. The moment you see that shape, a heap is the answer. A sorted array does the job but does it expensively; a balanced BST would also work but is heavier than you need.

The negation trick in Python (-stone to simulate max-heap with heapq) is worth internalizing. Python's heap module predates the language having a max-heap in the standard library, and the trick has been idiomatic for long enough that you'll see it everywhere. C#'s PriorityQueue with an explicit priority value is cleaner — you pass -stone as priority without touching the element itself.

Where this fits in the series

This is the second problem in the heap series, right after the first problem introduces the heap structure itself. What this problem adds is the "insert-back" move: you're not just extracting, you're modifying the extracted values and reinserting. That's the step up from a pure extraction problem.

The natural next problems are:

• LeetCode 215 — Kth Largest Element in an Array: you're extracting k times from a max-heap, no reinsert. Simpler loop, same extraction mechanics.
• LeetCode 703 — Kth Largest Element in a Stream: maintain a min-heap of size k to answer "what's the kth largest so far" on each insertion. The size constraint changes how you think about what to keep.
• LeetCode 621 — Task Scheduler: heap used to greedily pick the most frequent remaining task. The problem involves cooldowns, so you're also managing time slots — structurally more complex.
• LeetCode 1642 — Furthest Building You Can Reach: heap for selecting which jumps to "assign" a ladder to. Classic greedy plus heap combination.

Each of those adds one new wrinkle. Kth Largest adds a size constraint. Task Scheduler adds time. Furthest Building adds a choice constraint. Last Stone Weight is the clean version: just extract, compute, reinsert, repeat.