1046. Last Stone Weight
Asked at Apple, Salesforce
Difficulty
Easy
Time
O(n log n)
Space
O(n)
Pattern
Array
Companies
2
Problem
You are given an array stones, where each value is the weight of one stone. All weights are positive integers.
You play a game. On every turn, take the two heaviest stones still in play and smash them together. If their weights are equal, both stones are destroyed. If they are different, the lighter stone is destroyed and the heavier stone becomes the difference of the two weights.
Keep playing until at most one stone is left. Return the weight of that last stone, or return 0 if no stones remain.
Always smash the two heaviest stones
Constraints
- ●
1 <= stones.length <= 30 - ●
1 <= stones[i] <= 1000
Examples
stones = [2,7,4,1,8,1]1stones = [1]1Asked At
2 companies| 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.
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).
Max-heap keeps the heaviest stones on top
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
O(n log n) timeimport 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 runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.