Last Stone Weight - Solution & Explanation
Problem Statement
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:
- If
x == y, both stones are destroyed, and - If
x != y, the stone of weightxis destroyed, and the stone of weightyhas new weighty - 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] <= 1000
Approach Overview
Problem 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 1: Approach 1: Max-Heap based Simulation
This approach uses a max-heap (priority queue) to efficiently track and retrieve the two heaviest stones. By inserting stones with negative values, we use a min-heap implementation in certain languages to simulate max-heap behavior.
In this Python solution, we convert the stone weights into negative numbers to use heapq as a max-heap. We then repeatedly extract the two largest stones, compute their difference, and insert it back if it's non-zero.
Complexity
Time Complexity: O(n log n), where n is the number of stones. This accounts for the heap operations.
Space Complexity: O(n), to maintain the heap of stones.
Approach 2: Approach 2: Multi-Set/Bag with Sorting
This approach uses a multiset or bag (analogous to balanced trees or sorted lists in some languages) to manage dynamically sorted stone weights. This allows for direct access to largest elements and supports efficient inserts/removals without full re-sorting.
In this Python solution with sortedcontainers.SortedList, continuous access to sorted elements permits simplified removal of the heaviest stones, with sorted inserts enabling efficient management and updates of the list's order.
Complexity
Time Complexity: O(n^2), due to insert and remove operations in SortedList being O(log n).
Space Complexity: O(n), for storage within the SortedList.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Max-Heap based Simulation | Time Complexity: O(n log n), where n is the number of stones. This accounts for the heap operations. |
| Approach 2: Multi-Set/Bag with Sorting | Time Complexity: O(n^2), due to insert and remove operations in SortedList being O(log n). |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Last Stone Weight - Priority Queue - Leetcode 1046 - Python • NeetCode • 112,371 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Last Stone Weight easy or hard?
How to solve Last Stone Weight in O(n)?
What is the best approach for Last Stone Weight?
What data structure is used in Last Stone Weight?
What is the time complexity of Last Stone Weight?
Last Stone Weight Python or Java solution approach?
Is Last Stone Weight asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Last Stone Weight with our built-in code editor and test cases.
Practice on FleetCode