Pattern this teaches:Heap and Top K
Last Stone Weight
An easy Heap interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Heap
- Sheets
- 1
- Core for
- 10 roles
The problem
We have a collection of stones, each with a positive integer weight. In each turn, pick up the two heaviest stones and smash them together. If they have equal weight, both are destroyed; if they differ, the lighter stone is destroyed and the heavier stone gets reduced by the lighter stone's weight. Repeat until at most one stone remains. Return the weight of the last remaining stone, or 0 if none remain.
Example 1
- Input
- stones = [3,8,5,2,9,2]
- Output
- 1
- Why
- Smash 9 and 8 to get 1, remaining [3,5,2,2,1]. Smash 5 and 3 to get 2, remaining [2,2,2,1]. Smash 2 and 2 to get 0, remaining [2,1]. Smash 2 and 1 to get 1, remaining [1]. Last stone weight is 1.
Example 2
- Input
- stones = [1]
- Output
- 1
- Why
- Only one stone exists, so its weight is returned directly.
Example 3
- Input
- stones = [10,10]
- Output
- 0
- Why
- Both stones are equal weight, so both are destroyed, leaving nothing.
Constraints
- 1 <= stones.length <= 30
- 1 <= stones[i] <= 1000
How to think about it
Updated 2026-09-29Smashing two stones reduces the total count by either one or two every single round. You always need the absolute two heaviest available, and when they collide, the remainder re-enters the pool at an unpredictable rank. That dynamic top-two lookup is the textbook signature of a priority queue.
Approaches, worst first
Repeated full sort
time O(n^2 log n) · space O(n)
Sort the array descending, pop the two largest, push their positive difference back, and sort the entire array again. Simple to write, but wastes work repeatedly ordering undisturbed elements.
Max-heap simulationWrite this one
time O(n log n) · space O(n)
Heapify all stones into a max-heap. Pop two elements; if unequal, push the difference back. Each clash costs logarithmic time and shrinks the collection, leaving at most one element when the loop exits.
Where people lose marks · 3
- Returning an unhandled empty state. When the final two stones have equal weights, both vanish and the heap is completely empty, which must evaluate to 0 instead of popping undefined.
- Pushing a difference of zero back into the heap. Equal stones destroy each other entirely; inserting 0 pollutes the heap and inflates loop iterations.
- Assuming at least two stones exist initially. If stones has length 1, no smash ever occurs and that single stone must be returned immediately.
The theory behind it
Heap — the ground this problem stands on. All Heap problems
What Heap is
A heap is a specialized tree that keeps only the single most extreme item at the very top. In a min-heap, every parent node is smaller than its children, so the smallest element in the entire collection sits immediately at the root. Unlike a binary search tree, a heap does not keep all items in full sorted order. It maintains only a partial order, making it fast at giving you the single smallest or largest item without spending time sorting everything else.
When to reach for it
Reach for a heap when a problem asks for the top k largest elements, the kth smallest value, or a running median from a stream of numbers. Signals include phrases like continuously finding the cheapest item, merging k sorted linked lists, or scheduling tasks with priorities. Whenever you need repeated access to the minimum or maximum value while items are added and removed dynamically, a priority heap is the tool.
How the pattern works
To find the k largest elements, keep a min-heap of fixed size k. Push incoming numbers into the heap; whenever the heap size grows past k, pop the top item, which is the smallest among them. After processing all elements, only the k largest remain. For a running median, balance two heaps: a max-heap holding the smaller half of numbers and a min-heap holding the larger half. In code, heaps are stored compactly as flat arrays where a node at index i has children at indices 2i plus 1 and 2i plus 2.
More Heap problems
Target Roles
Core requirement for 10 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .