Watch 10 video solutions for Last Stone Weight, a easy level problem involving Array, Heap (Priority Queue). This walkthrough by NeetCode has 107,071 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array of integers stones where stones[i] is the weight of the ith stone.
We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:
x == y, both stones are destroyed, andx != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.At the end of the game, there is at most one stone left.
Return the weight of the last remaining stone. If there are no stones left, return 0.
Example 1:
Input: stones = [2,7,4,1,8,1] Output: 1 Explanation: We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then, we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then, we combine 2 and 1 to get 1 so the array converts to [1,1,1] then, we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.
Example 2:
Input: stones = [1] Output: 1
Constraints:
1 <= stones.length <= 301 <= stones[i] <= 1000Problem Overview: You are given a list of stone weights. Each turn, take the two heaviest stones and smash them together. If they are equal, both are destroyed. If not, the heavier stone becomes y - x. Continue until at most one stone remains, then return its weight. The core challenge is repeatedly finding and updating the two largest values efficiently.
Approach 1: Max-Heap based Simulation (O(n log n) time, O(n) space)
This approach models the process exactly as described using a heap (priority queue). Insert all stone weights into a max-heap so the largest element is always accessible in O(log n). Repeatedly extract the two largest stones, compute their difference, and push the remaining weight back into the heap if it is non-zero. Each smash operation involves two heap removals and possibly one insertion, all O(log n). Since at most n operations occur, the total complexity is O(n log n) with O(n) space for the heap. This approach is clean, efficient, and directly mirrors the problem's rules.
Approach 2: Multi-Set / Bag with Sorting (O(n log n) time, O(1)–O(n) space)
Another option is maintaining the stones in a sorted structure such as a multiset or repeatedly sorting an array. After sorting, the two largest values are at the end. Remove them, compute their difference, and insert the result back while maintaining sorted order. Using balanced tree structures or language-provided multisets keeps insertion and deletion at O(log n). If implemented with repeated sorting, each iteration costs O(n log n), which is less efficient but conceptually simple. The multiset version maintains the same asymptotic complexity as the heap solution but usually has slightly higher constant factors.
Recommended for interviews: The max-heap simulation is the expected solution. Interviewers want to see recognition that repeatedly extracting the largest elements is a priority queue problem. Mentioning a simple sorted-array simulation shows understanding of the mechanics, but implementing the heap-based approach demonstrates stronger command of data structures and produces the cleanest O(n log n) solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Max-Heap based Simulation | O(n log n) | O(n) | General case; best when you need repeated access to the largest elements |
| Multiset / Sorted Structure | O(n log n) | O(1)–O(n) | When language provides ordered multiset or tree structures |