Last Stone Weight
Problem
Given an array of integers stones representing the weights of stones, repeatedly smash the two heaviest stones until at most one stone remains, and return the weight of the remaining stone or 0 if none remain.
- 1 ≤ stones.length ≤ 30
- 1 ≤ stones[i] ≤ 1000
Example
stones = [2,7,4,1,8,1]1Initially, the two heaviest stones are 8 and 7. Smashing them yields a stone of weight 1 (8 - 7). The stones become [2,4,1,1,1]. Next, the two heaviest stones are 4 and 2. Smashing them yields 2 (4 - 2). The stones become [2,1,1,1]. Then, the two heaviest stones are 2 and 1. Smashing them yields 1 (2 - 1). The stones become [1,1,1]. Next, the two heaviest stones are 1 and 1. Smashing them destroys both. The stones become [1]. Only one stone remains with weight 1, which is returned.
Approach
Straightforward Solution
A brute-force approach would repeatedly sort the stones array to find the two heaviest stones, resulting in O(n log n) sorting per iteration and O(n² log n) overall time complexity, which is inefficient.
Core Observation
At each step, the two heaviest stones must be selected and smashed. This requires efficient retrieval of the maximum elements repeatedly, which suggests using a max heap data structure.
Path to Optimal
The key recognition signals are 'repeatedly select the two heaviest stones' and 'update the collection dynamically'. These indicate a heap or priority queue pattern because heaps provide O(log n) insertion and extraction of maximum elements. Using a max heap allows efficient retrieval and update of the stones after each smash, reducing the complexity significantly.
Optimal Approach
Transform the stones array into a max heap by negating the values (since Python's heapq is a min heap). Repeatedly pop the two largest stones, smash them, and if the result is non-zero, push it back into the heap. Continue until at most one stone remains. Return the absolute value of the remaining stone or 0 if none remain.
Time
O(n log n)
Building the heap takes O(n). Each smash operation involves two pops and possibly one push, each O(log n). Since there are at most n-1 smashes, total complexity is O(n log n).
Space
O(n)
The heap stores all stones, requiring O(n) auxiliary space proportional to the input size.
Pattern Spotlight
Heap / Priority Queue (Max Heap Simulation)
When a problem requires repeatedly extracting and updating the largest or smallest elements dynamically, simulate a max heap using a min heap with negated values to achieve efficient O(log n) operations.
Solution
| 1 | import heapq
|
| 2 |
|
| 3 | class Solution:
|
| 4 | def lastStoneWeight(self, stones: list[int]) -> int:
|
| 5 | max_heap = [-s for s in stones]
|
| 6 | heapq.heapify(max_heap)
|
| 7 |
|
| 8 | while len(max_heap) > 1:
|
| 9 | first = heapq.heappop(max_heap)
|
| 10 | second = heapq.heappop(max_heap)
|
| 11 | if second > first:
|
| 12 | heapq.heappush(max_heap, first - second)
|
| 13 |
|
| 14 | max_heap.append(0)
|
| 15 | return abs(max_heap[0]) |
| 1 | import java.util.PriorityQueue; |
| 2 | import java.util.Collections; |
| 3 | |
| 4 | class Solution { |
| 5 | public int lastStoneWeight(int[] stones) { |
| 6 | PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); |
| 7 | for (int stone : stones) { |
| 8 | maxHeap.offer(stone); |
| 9 | } |
| 10 | |
| 11 | while (maxHeap.size() > 1) { |
| 12 | int first = maxHeap.poll(); |
| 13 | int second = maxHeap.poll(); |
| 14 | if (first != second) { |
| 15 | maxHeap.offer(first - second); |
| 16 | } |
| 17 | } |
| 18 | |
| 19 | if (maxHeap.isEmpty()) { |
| 20 | maxHeap.offer(0); |
| 21 | } |
| 22 | return Math.abs(maxHeap.peek()); |
| 23 | } |
| 24 | } |
| 1 | #include <vector> |
| 2 | #include <queue> |
| 3 | #include <algorithm> |
| 4 | |
| 5 | using namespace std; |
| 6 | |
| 7 | class Solution { |
| 8 | public: |
| 9 | int lastStoneWeight(vector<int>& stones) { |
| 10 | priority_queue<int> maxHeap; |
| 11 | for (int stone : stones) { |
| 12 | maxHeap.push(stone); |
| 13 | } |
| 14 | |
| 15 | while (maxHeap.size() > 1) { |
| 16 | int first = maxHeap.top(); |
| 17 | maxHeap.pop(); |
| 18 | int second = maxHeap.top(); |
| 19 | maxHeap.pop(); |
| 20 | if (first != second) { |
| 21 | maxHeap.push(first - second); |
| 22 | } |
| 23 | } |
| 24 | |
| 25 | if (maxHeap.empty()) { |
| 26 | maxHeap.push(0); |
| 27 | } |
| 28 | return abs(maxHeap.top()); |
| 29 | } |
| 30 | }; |
| 1 | class Solution { |
| 2 | lastStoneWeight(stones) { |
| 3 | const maxHeap = []; |
| 4 | |
| 5 | // Helper functions for max heap |
| 6 | function heapify(arr) { |
| 7 | for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) { |
| 8 | siftDown(arr, i, arr.length); |
| 9 | } |
| 10 | } |
| 11 | |
| 12 | function siftDown(heap, i, n) { |
| 13 | let largest = i; |
| 14 | const left = 2 * i + 1; |
| 15 | const right = 2 * i + 2; |
| 16 | |
| 17 | if (left < n && heap[left] > heap[largest]) { |
| 18 | largest = left; |
| 19 | } |
| 20 | if (right < n && heap[right] > heap[largest]) { |
| 21 | largest = right; |
| 22 | } |
| 23 | if (largest !== i) { |
| 24 | [heap[i], heap[largest]] = [heap[largest], heap[i]]; |
| 25 | siftDown(heap, largest, n); |
| 26 | } |
| 27 | } |
| 28 | |
| 29 | function heapPop(heap) { |
| 30 | const top = heap[0]; |
| 31 | const last = heap.pop(); |
| 32 | if (heap.length > 0) { |
| 33 | heap[0] = last; |
| 34 | siftDown(heap, 0, heap.length); |
| 35 | } |
| 36 | return top; |
| 37 | } |
| 38 | |
| 39 | function heapPush(heap, val) { |
| 40 | heap.push(val); |
| 41 | let i = heap.length - 1; |
| 42 | while (i > 0) { |
| 43 | const parent = Math.floor((i - 1) / 2); |
| 44 | if (heap[parent] >= heap[i]) break; |
| 45 | [heap[parent], heap[i]] = [heap[i], heap[parent]]; |
| 46 | i = parent; |
| 47 | } |
| 48 | } |
| 49 | |
| 50 | for (const stone of stones) { |
| 51 | heapPush(maxHeap, stone); |
| 52 | } |
| 53 | |
| 54 | while (maxHeap.length > 1) { |
| 55 | const first = heapPop(maxHeap); |
| 56 | const second = heapPop(maxHeap); |
| 57 | if (first !== second) { |
| 58 | heapPush(maxHeap, first - second); |
| 59 | } |
| 60 | } |
| 61 | |
| 62 | if (maxHeap.length === 0) { |
| 63 | maxHeap.push(0); |
| 64 | } |
| 65 | return Math.abs(maxHeap[0]); |
| 66 | } |
| 67 | } |
Step-by-Step Solution
Build a Max Heap by Negating Stone Weights
| 5 | max_heap = [-s for s in stones]
|
| 6 | heapq.heapify(max_heap)
|
Objective
To create a max heap from the stones array by negating the values and heapifying.
Key Insight
Python's heapq module implements a min heap, so negating the stone weights transforms the problem into a min heap of negative values, effectively simulating a max heap. This allows efficient extraction of the largest stones using heap operations.
Interview Quick-Check
Core Logic
Negating values transforms the problem into a min heap of negative numbers, enabling max heap behavior with Python's heapq.
Common Pitfalls & Bugs
Forgetting to negate values leads to extracting the smallest stones instead of the largest, breaking the logic.
Simulate Stone Smashing by Extracting and Combining the Two Largest Stones
| 8 | while len(max_heap) > 1:
|
| 9 | first = heapq.heappop(max_heap)
|
| 10 | second = heapq.heappop(max_heap)
|
| 11 | if second > first:
|
| 12 | heapq.heappush(max_heap, first - second)
|
Objective
To repeatedly extract the two largest stones, smash them, and push the difference back if non-zero.
Key Insight
By popping the two smallest negative values (which correspond to the two largest stones), the algorithm simulates smashing. If the stones differ, the difference is pushed back as a negative value to maintain the max heap property. This loop continues until at most one stone remains, ensuring the correct final result.
Interview Quick-Check
Core Logic
Repeatedly pop two largest stones (smallest negatives), smash them, and push the difference if non-zero to simulate the problem's process efficiently.
State & Boundaries
The loop continues while there are at least two stones, ensuring all possible smashes are performed.
Common Pitfalls & Bugs
Incorrectly comparing popped values without considering negation can cause logic errors.
Handle the Final Stone or Return Zero if None Remain
| 14 | max_heap.append(0)
|
| 15 | return abs(max_heap[0]) |
Objective
To return the weight of the last remaining stone or zero if no stones remain.
Key Insight
Appending zero ensures the heap is never empty when accessing the last element, simplifying the return statement. Taking the absolute value converts the stored negative value back to the original positive weight.
Interview Quick-Check
Core Logic
Appending zero guarantees a valid return value even if the heap is empty, avoiding index errors.
Common Pitfalls & Bugs
Failing to take the absolute value would return a negative weight, which is incorrect.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
max_heap = [-s for s in stones]Create a list of negated stone weights to simulate a max heap using Python's min heap.
Negating the stone weights transforms the problem into a min heap of negative values, allowing efficient extraction of the largest stones using heapq, which only supports min heaps.
first = heapq.heappop(max_heap)Extract the largest stone (smallest negative value) from the heap.
Popping the smallest negative value corresponds to removing the heaviest stone, which is essential for simulating the stone smashing process correctly.
second = heapq.heappop(max_heap)Extract the second largest stone from the heap.
Removing the second heaviest stone allows the algorithm to simulate the smash between the two largest stones at each iteration.
heapq.heappush(max_heap, first - second)Push the difference of the two stones back into the heap if non-zero.
Pushing the difference maintains the heap property and ensures the simulation continues correctly with the updated stone weights after smashing.
heapq.heapify(max_heap)Transform the negated stones list into a heap in-place.
Heapifying the list organizes it into a valid heap structure, enabling O(log n) insertion and extraction operations necessary for efficient repeated stone smashing.
if second > first:Check if the two stones have different weights (considering negation).
Comparing the negative values correctly identifies if the stones differ, which determines whether a new stone (the difference) should be pushed back into the heap.
return abs(max_heap[0])Return the absolute value of the last remaining stone's weight or zero.
Taking the absolute value converts the stored negative weight back to the original positive stone weight, providing the correct final result.
while len(max_heap) > 1:Continue the smashing process while there are at least two stones in the heap.
The loop condition ensures that smashing occurs only when two stones are available, preventing invalid operations and correctly terminating when one or no stones remain.
max_heap.append(0)Append zero to the heap to handle the case when no stones remain.
Appending zero guarantees that accessing the first element of the heap is always safe, preventing index errors when the heap is empty after all smashes.
Test Your Understanding
Why is a max heap (or simulated max heap) the appropriate data structure for this problem?
Because the problem requires repeatedly extracting the two largest stones efficiently, and a max heap provides O(log n) time for both extraction and insertion, enabling an efficient simulation of the smashing process.
Related Problems
Heaps pattern
Don't just read it. Drill it.
Reconstruct Last Stone Weight from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Last Stone Weight drill