1046. Last Stone Weight
Problem Description
In this problem, we have a collection of stones with different weights, given in an array stones
, where each stone's weight is represented by stones[i]
. We are simulating a game where we repeatedly smash the two heaviest stones together and determine the outcome according to the following rules:
- If both stones have the same weight (
x == y
), both stones get completely destroyed. - If the weights are different (
x != y
), the lighter stone gets destroyed, and the weight of the heavier stone gets reduced by that of the lighter stone (y - x
).
The game continues until there is either one stone left or no stones remaining. The goal is to return the weight of the last remaining stone. If there are no stones left as a result of the smashes, we should return 0
.
Intuition
The solution requires us to repeatedly find and remove the two heaviest stones. Since we need to do this repeatedly, a heap is an ideal data structure as it allows for efficient retrieval and updating of the largest elements.
A max heap keeps the maximum element at the top. However, Python's heapq
module provides a min heap, so we insert the negative of stone weights to simulate the behavior of a max heap.
Here is the step-by-step approach to the solution:
- Convert all stone weights to their negative and create a min heap. This negation is necessary because the Python
heapq
module only supports min heaps. - While there are at least two stones in the heap:
- Pop the heaviest stone (which is the smallest in the min heap due to negation) and store its negated value in
y
. - Pop the second heaviest stone (again the smallest in our min heap) and store its negated value in
x
. - If
x
andy
are not equal, we push the weight difference negated (x - y
) back onto the heap since stonex
got destroyed and the weight of stoney
reduced byx
.
- Pop the heaviest stone (which is the smallest in the min heap due to negation) and store its negated value in
- After the loop, if the heap is empty, it means no stones are left and we return
0
. Else, we return the negation of the weight of the last stone left in the heap (as we stored negative values, we need to negate it back to return the actual weight).
Using this approach, we efficiently simulate the stone smashing game and find the weight of the last stone or determine that no stones are left.
Learn more about Heap (Priority Queue) patterns.
Solution Approach
The method lastStoneWeight
is implemented using a min heap to efficiently manage the stones according to their weights.
Here's a breakdown of the solution:
- A min heap is created from the list of stones. Each stone's weight is negated prior to insertion because Python's heapq module works as a min heap. A min heap allows quick access to the smallest element, so by negating the weights, we get quick access to the largest element.
1h = [-x for x in stones] 2heapify(h)
-
The solution iteratively processes the heap until there’s one or zero stones left. This is handled by a while loop that continues as long as the length of the heap (
h
) is greater than one. -
Inside the loop, the two heaviest stones (which are actually the two smallest values in the heap due to negation) are popped from the heap. This is done using
heappop(h)
, and the negated value of the pops representsy
andx
.
1y, x = -heappop(h), -heappop(h)
- If the weight of the two stones is not equal (
x != y
), it means that after smashing the stones, one of them (the lighter stonex
) is completely destroyed, while the other (y
) is reduced in weight. The difference (y - x
) is computed, negated, and pushed back into the heap.
1if x != y: 2 heappush(h, x - y)
- After the loop exits, which happens when only one stone is left or none at all, the function checks if the heap is empty. If it is empty (
not h
), the function returns0
. Otherwise, it returns the weight of the last stone left, negating it to convert it back to the original weight value.
1return 0 if not h else -h[0]
Using heapq for maintaining a heap and negating values is an efficient approach to simulate a max heap in Python. This problem showcases an excellent use of the heap data structure to solve a problem related to constant removal and insertion of elements to achieve a sorted characteristic (largest or smallest).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach:
Suppose we have an array of stone weights stones = [2, 7, 4, 1, 8, 1]
. We need to perform the following steps:
-
Convert the weights to their negative and create a min heap:
- We negate the weights:
[-2, -7, -4, -1, -8, -1]
- Create a min heap from these negated weights:
h = [-8, -7, -4, -1, -2, -1]
- We negate the weights:
-
While there are at least two stones in the heap:
- Pop the heaviest stone (smallest in negated form):
y = -heappop(h)
gives usy = 8
, and nowh = [-7, -2, -4, -1, -1]
- Pop the second heaviest stone:
x = -heappop(h)
gives usx = 7
, and nowh = [-4, -2, -1, -1]
- Push the weight difference negated back onto the heap since
x != y
:- The difference is
8 - 7 = 1
. After negating, we push-1
back onto the heap. - Now,
h = [-4, -2, -1, -1, -1]
- The difference is
- Pop the heaviest stone (smallest in negated form):
-
Repeat the process:
- Next,
y = -heappop(h)
gives usy = 4
,h = [-2, -1, -1, -1]
- Then,
x = -heappop(h)
gives usx = 2
,h = [-1, -1, -1]
- The difference is
4 - 2 = 2
. After negating, we push-2
back onto the heap. - Now,
h = [-2, -1, -1]
- Next,
-
Continue:
- Next,
y = -heappop(h)
gives usy = 2
,h = [-1, -1]
- Then,
x = -heappop(h)
gives usx = 1
,h = [-1]
- The difference is
2 - 1 = 1
. After negating, we push-1
back onto the heap. - Now,
h = [-1, -1]
- Next,
-
Final iterations will destroy both of the stones because they have the same weight:
- Next,
y = -heappop(h)
gives usy = 1
,h = [-1]
- Then,
x = -heappop(h)
gives usx = 1
,h = []
- Since
x == y
, we don't push anything back onto the heap.
- Next,
-
Now the heap is empty (
h = []
), that is, no stones are left. We return0
.
The final result for the example input stones = [2, 7, 4, 1, 8, 1]
is 0
, as all stones are eventually destroyed.
Solution Implementation
1from heapq import heapify, heappush, heappop
2
3class Solution:
4 def lastStoneWeight(self, stones: List[int]) -> int:
5 # Create a max heap by inverting the values of the stones
6 max_heap = [-stone for stone in stones]
7 heapify(max_heap)
8
9 # Continue processing until there is one or no stones left
10 while len(max_heap) > 1:
11 # Pop the two largest stones from the heap
12 # Stones are negated again to get their original values
13 stone1 = -heappop(max_heap)
14 stone2 = -heappop(max_heap)
15
16 # If the largest stones are not of the same weight
17 if stone1 != stone2:
18 # The result of the collision is added back to the heap
19 heappush(max_heap, -(stone1 - stone2))
20
21 # If the heap is empty, return 0; else return the weight of the last stone
22 return 0 if not max_heap else -max_heap[0]
23
1class Solution {
2 /**
3 * Simulate the process of smashing stones together and return
4 * the weight of the last remaining stone (if any).
5 *
6 * @param stones An array of stone weights.
7 * @return The weight of the last stone, or 0 if no stones are left.
8 */
9 public int lastStoneWeight(int[] stones) {
10 // Create a max-heap to store and compare the stone weights in descending order
11 PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
12
13 // Add all stone weights to the max-heap
14 for (int stone : stones) {
15 maxHeap.offer(stone);
16 }
17
18 // Continue until there is only one stone left or none at all
19 while (maxHeap.size() > 1) {
20 // Get the two heaviest stones
21 int stoneOne = maxHeap.poll();
22 int stoneTwo = maxHeap.poll();
23
24 // If they are not the same weight, put the difference back into the max-heap
25 if (stoneOne != stoneTwo) {
26 maxHeap.offer(stoneOne - stoneTwo);
27 }
28 // If they are equal, both stones are completely smashed, and nothing is added back
29 }
30
31 // Return the last stone's weight or 0 if no stones are left
32 return maxHeap.isEmpty() ? 0 : maxHeap.poll();
33 }
34}
35
1#include <vector>
2#include <queue>
3
4class Solution {
5public:
6 // Function to return the last stone's weight after smashing the largest two until one or none are left
7 int lastStoneWeight(vector<int>& stones) {
8 // Priority queue to store the stones with max heap property to easily retrieve the heaviest stones
9 priority_queue<int> maxHeap;
10
11 // Insert all stones into the priority queue
12 for (int stone : stones) {
13 maxHeap.push(stone);
14 }
15
16 // Loop until there is only one stone left or none
17 while (maxHeap.size() > 1) {
18 // Take out the heaviest stone
19 int heaviestStone = maxHeap.top();
20 maxHeap.pop();
21
22 // Take out the second heaviest stone
23 int secondHeaviestStone = maxHeap.top();
24 maxHeap.pop();
25
26 // If the two stones have different weights, push the difference back into the queue
27 if (heaviestStone != secondHeaviestStone) {
28 maxHeap.push(heaviestStone - secondHeaviestStone);
29 }
30
31 // If the stones have the same weight, both get destroyed and nothing goes back into the queue
32 }
33
34 // If there are no stones left, return 0, otherwise return the weight of the remaining stone
35 return maxHeap.empty() ? 0 : maxHeap.top();
36 }
37};
38
1// Import the necessary module for Priority Queue
2import { MaxPriorityQueue } from '@datastructures-js/priority-queue';
3
4/**
5 * Simulates a process where stones smash each other. If two stones have
6 * different weights, the weight of the smaller one is subtracted from the other.
7 * The smaller stone is then considered destroyed. The process repeats until
8 * there is one stone left or none. The function returns the weight of the remaining
9 * stone, or 0 if none are left.
10 * @param {number[]} stones - An array of stone weights.
11 * @return {number} The weight of the last remaining stone, or 0 if none.
12 */
13function getLastStoneWeight(stones: number[]): number {
14 // Initialize a max priority queue for the stones
15 const priorityQueue = new MaxPriorityQueue<number>();
16
17 // Enqueue all the stones to the priority queue
18 for (const stone of stones) {
19 priorityQueue.enqueue(stone);
20 }
21
22 // Loop until there is either one stone left or none
23 while (priorityQueue.size() > 1) {
24 // Dequeue the two heaviest stones
25 const heavierStone = priorityQueue.dequeue().element;
26 const lighterStone = priorityQueue.dequeue().element;
27
28 // If there is a weight difference, enqueue the difference as a new stone
29 if (heavierStone !== lighterStone) {
30 priorityQueue.enqueue(heavierStone - lighterStone);
31 }
32 }
33
34 // If the priority queue is empty, return 0; otherwise, return the weight of the last stone
35 return priorityQueue.isEmpty() ? 0 : priorityQueue.dequeue().element;
36}
37
Time and Space Complexity
The given code implements a heap to solve the last stone weight problem. Let's analyze both the time complexity and the space complexity of the given code.
Time Complexity
The main operations in the algorithm are:
- Converting the
stones
list into a heap which takesO(n)
time, wheren
is the number of stones. - The
while
loop. In the worst case, the heap containsn - 1
elements, andheappop()
is called twice per iteration. Since eachheappop()
operation takesO(log n)
time, and in each iteration, we might do aheappush()
which also takesO(log n)
time. - The loop runs at most
n - 1
times because in each iteration at least one stone is removed.
Putting it all together, the worst-case scenario would involve (2 * log n + log n)
operations per iteration due to two heappop()
calls and one potential heappush()
call, across n - 1
iterations. Hence, the total time complexity is O(n log n)
.
Space Complexity
The space complexity consists of:
- The heap
h
which stores at mostn
integers, thus requiringO(n)
space. - Constant extra space for variables
x
andy
.
So, the overall space complexity of the algorithm is O(n)
since the heap size is proportional to the input size, and other space usage is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.