Last Stone Weight — Solution

Problem

You have a collection of stones with positive integer weights. Each round, pick the two heaviest stones and smash them together: if they weigh the same, both are destroyed; if they differ, the lighter one is destroyed and the heavier one survives with its weight reduced by the lighter stone's weight. Repeat until at most one stone remains and return its weight, or 0 if nothing is left.

• Input: stones = [2, 7, 4, 1, 8, 1]
• Output: 1
• Explanation: smash 8 and 7 → 1 remains; smash 4 and 2 → 2 remains; smash 2 and 1 → 1 remains; smash 1 and 1 → both destroyed. One stone of weight 1 survives.

Intuition

Every round demands the two current maximum values — an inherently dynamic query because the heap changes after each smash. A max-heap delivers each maximum in O(log n) and re-inserts the remainder stone in O(log n), so each round costs O(log n) instead of an O(n) linear scan through the whole collection.

Solution — Max-Heap

Push all stones onto a max-heap, then repeatedly pop the two heaviest and push back their difference if they are unequal. Stop when one or zero stones remain.

1. Build a max-heap from all stone weights.
2. While more than one stone is in the heap: a. Pop the heaviest stone. b. Pop the second-heaviest stone. c. If they differ, push heaviest − second_heaviest back onto the heap.
3. Return the remaining stone's weight, or 0 if the heap is empty.

1import heapq
2
3def lastStoneWeight(stones: list[int]) -> int:
4    max_heap = [-stone for stone in stones]  # negate to simulate max-heap with Python's min-heap
5    heapq.heapify(max_heap)
6
7    while len(max_heap) > 1:
8        heaviest = -heapq.heappop(max_heap)
9        second_heaviest = -heapq.heappop(max_heap)
10        if heaviest != second_heaviest:
11            heapq.heappush(max_heap, -(heaviest - second_heaviest))  # remainder stone survives
12
13    return -max_heap[0] if max_heap else 0

Time: O(n log n) — heapify is O(n) and each of at most n rounds performs two pops and one push, each O(log n).

Space: O(n) — the heap stores all stones simultaneously.

Complexity Summary

Common Mistakes

• Forgetting to negate values in Python — heapq is a min-heap, so storing stone instead of -stone causes the lightest stones to be smashed each round, producing completely wrong results.
• Not guarding against an empty heap after the loop — when every smash produces equal-weight pairs, all stones cancel out and the heap ends up empty; reading heap[0] on an empty structure crashes.
• Pushing the remainder even when both stones are equal — equal stones destroy each other entirely and produce nothing; pushing a weight of 0 corrupts the heap and can cause the loop to run one extra iteration.
• Re-sorting the array each round instead of using a heap — sorting after every smash costs O(n log n) per round and O(n² log n) total; a heap reduces per-round work to O(log n).
• Checking len > 0 as the loop condition — the loop needs at least two elements to smash; exiting at len == 1 is correct, but len > 0 would try to pop a second stone from a single-element heap.

Related Problems

• Kth Largest Element in an Array — uses a heap to efficiently surface the kth largest without a full sort
• Top K Frequent Elements — heap-based selection of the k most frequent elements from a dynamic count
• K Closest Points to Origin — selects k smallest elements using a heap keyed on distance
• Merge K Sorted Lists — min-heap merges multiple sorted sequences by always popping the current global minimum
• Find K Closest Elements — heap-based selection ordered by absolute difference from a target