Last Stone Weight
Understanding the Problem
We simulate a process: repeatedly pick the two heaviest stones, smash them, and put the result back if anything remains. This continues until one or zero stones are left.
The work each round is to find the two largest elements. After removing them and possibly inserting a new value, we need the two largest again. Sorting every round solves this, but a max-heap (priority queue) supports repeated extraction of the maximum at lower cost.
Key Constraints:
1 <= stones.length <= 30→ The input is small, so an O(n^2 log n) approach also passes. The constraint does not rule out any of the approaches below; it only means the simulation always terminates quickly.1 <= stones[i] <= 1000→ All weights are positive integers. The differencey - xis always non-negative, and the smashed valuey - x < y, so the maximum weight never increases and the heap or list strictly shrinks (one stone removed each round). The simulation runs at most n - 1 rounds.
Approach 1: Sorting
Intuition
Sorting the array puts the two heaviest stones at the end. We smash them, compute the difference, remove both, and if the difference is non-zero, insert it back. Then we sort again and repeat until one or zero stones remain.
This re-sorts the whole array every round, which is wasteful, but with n up to 30 it runs fast and is easy to reason about.
Algorithm
- While the list has more than one stone:
- Sort the list.
- Take the last two elements (the two heaviest).
- Remove them both from the list.
- If they are not equal, add the difference back to the list.
- If one stone remains, return its weight. Otherwise, return 0.
Example Walkthrough
Code
- Time Complexity: O(n^2 log n). We perform at most n rounds. Each round sorts the list, which costs O(n log n). So the total is O(n * n log n) = O(n^2 log n).
- Space Complexity: O(n). We store the stones in a list that shrinks over time, using at most O(n) space.
Sorting the entire list every round to find two elements is the bottleneck. A max-heap keeps the maximum accessible without re-sorting, which removes that cost.
Approach 2: Max-Heap (Optimal)
Intuition
A max-heap supports extracting the maximum in O(log n) and inserting a new element in O(log n). Instead of sorting every round, we build the heap once, then repeatedly extract the two largest, smash them, and push the result back. Each round costs O(log n) instead of O(n log n) for a full re-sort.
The default heap direction differs by language. C++ priority_queue and Rust BinaryHeap are max-heaps. Java PriorityQueue and C# PriorityQueue are min-heaps, so we either pass a reverse comparator or use a negated priority. Python heapq is a min-heap, so we negate the stored values: push -stone, and negate again when popping to recover the original weight.
Algorithm
- Build a max-heap from all the stones.
- While the heap has more than one element:
- Extract the two largest values (y and x, with y >= x).
- If y != x, push (y - x) back into the heap.
- If the heap has one element, return it. Otherwise, return 0.
Example Walkthrough
Code
- Time Complexity: O(n log n). Building the heap takes O(n). Each round does two extractions and at most one insertion, each O(log n). We have at most n rounds, so the total is O(n log n).
- Space Complexity: O(n). The heap stores all the stones, using O(n) space.