Last Stone Weight
Asked at Apple, Salesforce
Problem
You have stones with positive integer weights. Each turn, smash the two heaviest stones together. If they are equal, both are destroyed. If not, the lighter one is destroyed and the heavier one's weight is reduced by the lighter's weight. Continue until at most one stone remains. Return its weight. Use a max-heap to always access the two heaviest stones.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | Easy | View all Apple questions → |
| Salesforce | Easy | View all Salesforce questions → |
How to Think About It
Key insight: at each step, you need the two heaviest stones. A max-heap gives you both in O(log n) time. Smash them, and if there's a remainder, push it back into the heap.
Visual walkthrough for [2, 7, 4, 1, 8, 1]:
- Max-heap: [8, 7, 4, 2, 1, 1]
- Smash 8 and 7: 8-7=1. Push 1. Heap: [4, 2, 1, 1, 1]
- Smash 4 and 2: 4-2=2. Push 2. Heap: [2, 1, 1, 1]
- Smash 2 and 1: 2-1=1. Push 1. Heap: [1, 1, 1]
- Smash 1 and 1: equal, both destroyed. Heap: [1]
`- Only one stone left. Return 1.
Python's heapq is a min-heap. To simulate a max-heap, negate all values before pushing. When popping, negate again to get the original value. This is a standard trick.
The algorithm: build a max-heap from the stones. While heap has more than one stone:
- Pop two largest stones.
- If they are not equal, push the difference back.
`- If heap is empty, return 0. Otherwise return the remaining stone.
Edge cases: single stone (return it immediately), all stones equal (they all destroy each other, return 0), two different stones (return the difference).
Time: O(n log n) — each heap operation is O(log n), and we do at most n-1 smashes. Space: O(n) for the heap.
Optimal Approach
Build a max-heap by negating all stone weights. While the heap has more than one element:
- Pop two largest stones (negate to get original values).
- If they are not equal, push the absolute difference (negated) back.
- If the heap is empty, return 0.
- Otherwise, return the negation of the remaining element.
Walkthrough with [2, 7, 4, 1, 8, 1]:
- Negate: [-8, -7, -4, -2, -1, -1]
- Pop -8 and -7: 8 != 7, push -(8-7) = -1. Heap: [-4, -2, -1, -1, -1]
- Pop -4 and -2: 4 != 2, push -(4-2) = -2. Heap: [-2, -1, -1, -1]
- Pop -2 and -1: 2 != 1, push -(2-1) = -1. Heap: [-1, -1, -1]
- Pop -1 and -1: equal, both destroyed. Heap: [-1]
- Return -(-1) = 1.
Time: O(n log n). Space: O(n).
What Trips People Up in Real Interviews
Forgetting to handle the case where the heap becomes empty. If all stones are destroyed (equal pairs), the heap is empty and you should return 0, not access the top element.
Using a min-heap in Python without negating values. Python's heapq is a min-heap. If you push positive values, heappop returns the smallest, not the largest. Negate values to simulate a max-heap.
Not pushing the difference back when stones are unequal. After smashing, if the heavier stone survives, push its remaining weight back into the heap. Forgetting this step breaks the simulation.
Trying to sort the array instead of using a heap. Sorting is O(n log n) but you'd need to re-sort after each smash. A heap gives O(log n) per smash, which is more efficient.
Confusing the smash rule. The heavier stone survives with weight (heavier - lighter). Both stones are destroyed only if they are equal. Don't push 0 when they are equal.
Solution Code
import heapq
def lastStoneWeight(stones):
max_heap = [-s for s in stones]
heapq.heapify(max_heap)
while len(max_heap) > 1:
first = -heapq.heappop(max_heap)
second = -heapq.heappop(max_heap)
if first != second:
heapq.heappush(max_heap, -(first - second))
return -max_heap[0] if max_heap else 0Frequently Asked Questions
What is the Last Stone Weight problem?
You have stones with positive integer weights. Each turn, smash the two heaviest stones together. If they are equal, both are destroyed. If not, the lighter one is destroyed and the heavier one's weight is reduced by the lighter's weight. Continue until at most one stone remains. Return its weight. Use a max-heap to always access the two heaviest stones.
How do you solve Last Stone Weight?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Last Stone Weight?
Last Stone Weight is asked at Apple, Salesforce. It is a easy difficulty problem.
What are common mistakes on Last Stone Weight?
- Forgetting to handle the case where the heap becomes empty. If all stones are destroyed (equal pairs), the heap is empty and you should return 0, not access the top element.
- Using a min-heap in Python without negating values. Python's `heapq` is a min-heap. If you push positive values, `heappop` returns the smallest, not the largest. Negate values to simulate a max-heap.
- Not pushing the difference back when stones are unequal. After smashing, if the heavier stone survives, push its remaining weight back into the heap. Forgetting this step breaks the simulation.
- Trying to sort the array instead of using a heap. Sorting is `O(n log n)` but you'd need to re-sort after each smash. A heap gives `O(log n)` per smash, which is more efficient.
- Confusing the smash rule. The heavier stone survives with weight (heavier - lighter). Both stones are destroyed only if they are equal. Don't push 0 when they are equal.