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] <= 1000This 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.
Java
C++
C#
JavaScript
C
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.
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.
Java
C++
C#
JavaScript
C
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 | 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). |
Last Stone Weight - Priority Queue - Leetcode 1046 - Python • NeetCode • 85,324 views views
Watch 9 more video solutions →Practice Last Stone Weight with our built-in code editor and test cases.
Practice on FleetCode