Last Stone Weight
Last Stone Weight is a easy heaps problem solved with the top k / kth largest / smallest pattern.
The best approach, optimal (max-heap), runs in O(n log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (sort every round) up.
Problem
You have a pile of stones, where stones[i] is the weight of the i-th stone. On each turn you take the two heaviest stones, with weights y >= x, and smash them together:
- if
x == y, both stones are destroyed; - otherwise the lighter stone is destroyed and the heavier one now weighs
y - x.
Keep going until at most one stone is left. Return the weight of that stone, or 0 if no stones remain.
Examples
Example 1
- Input
stones = [4, 9, 3, 6]- Output
2- Why
- 9 and 6 leave 3 → [4, 3, 3]; 4 and 3 leave 1 → [3, 1]; 3 and 1 leave 2 → [2].
Example 2
- Input
stones = [5, 5]- Output
0- Why
- Equal stones destroy each other, so nothing is left.
Example 3
- Input
stones = [8]- Output
8- Why
- A single stone is never smashed.
Constraints
1 <= stones.length <= 301 <= stones[i] <= 1000
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (sort every round) | O(n² log n) | O(n) |
| Optimal (max-heap) | O(n log n) | O(n) |
1Brute force (sort every round)
O(n² log n)Up to n rounds, each sorting up to n stones.O(n)The working list.Keep the stones in a list. Each round, sort it, take the two largest, and put back their difference if it is positive. Stop when at most one stone is left.
- Copy the stones into a list.
- While the list has at least two stones: sort it, remove the last two values y >= x.
- If y > x, add y - x back to the list.
- Return the remaining stone, or 0 if the list is empty.
class Solution {
public int lastStoneWeight(int[] stones) {
List<Integer> list = new ArrayList<>();
for (int s : stones) list.add(s);
while (list.size() > 1) {
Collections.sort(list);
int y = list.remove(list.size() - 1);
int x = list.remove(list.size() - 1);
if (y > x) list.add(y - x);
}
return list.isEmpty() ? 0 : list.get(0);
}
}class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
lst = list(stones)
while len(lst) > 1:
lst.sort()
y = lst.pop()
x = lst.pop()
if y > x:
lst.append(y - x)
return lst[0] if lst else 0class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
vector<int> list(stones.begin(), stones.end());
while (list.size() > 1) {
sort(list.begin(), list.end());
int y = list.back(); list.pop_back();
int x = list.back(); list.pop_back();
if (y > x) list.push_back(y - x);
}
return list.empty() ? 0 : list[0];
}
};function lastStoneWeight(stones) {
const list = [...stones];
while (list.length > 1) {
list.sort((a, b) => a - b);
const y = list.pop();
const x = list.pop();
if (y > x) list.push(y - x);
}
return list.length === 0 ? 0 : list[0];
}2Optimal (max-heap)
O(n log n)Each round removes at least one stone, so there are at most n rounds of O(log n) heap work.O(n)The heap holds up to n stones.A max-heap always hands out the current heaviest stone in O(log n). Pop the two heaviest, push back their difference when it is non-zero, and repeat until at most one stone remains.
- Push every stone into a max-heap.
- While the heap has at least two stones: pop y, pop x.
- If y != x, push y - x.
- Return the top of the heap, or 0 if it is empty.
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int s : stones) pq.offer(s);
while (pq.size() > 1) {
int y = pq.poll(), x = pq.poll();
if (y != x) pq.offer(y - x);
}
return pq.isEmpty() ? 0 : pq.peek();
}
}class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
heap = [-s for s in stones]
heapq.heapify(heap)
while len(heap) > 1:
y = -heapq.heappop(heap)
x = -heapq.heappop(heap)
if y != x:
heapq.heappush(heap, -(y - x))
return -heap[0] if heap else 0class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> pq(stones.begin(), stones.end());
while (pq.size() > 1) {
int y = pq.top(); pq.pop();
int x = pq.top(); pq.pop();
if (y != x) pq.push(y - x);
}
return pq.empty() ? 0 : pq.top();
}
};function lastStoneWeight(stones) {
// small binary max-heap
const h = [];
const push = (v) => {
h.push(v);
let i = h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (h[p] >= h[i]) break;
[h[p], h[i]] = [h[i], h[p]];
i = p;
}
};
const pop = () => {
const top = h[0];
const last = h.pop();
if (h.length > 0) {
h[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < h.length && h[l] > h[m]) m = l;
if (r < h.length && h[r] > h[m]) m = r;
if (m === i) break;
[h[m], h[i]] = [h[i], h[m]];
i = m;
}
}
return top;
};
for (const s of stones) push(s);
while (h.length > 1) {
const y = pop(), x = pop();
if (y !== x) push(y - x);
}
return h.length === 0 ? 0 : h[0];
}Edge cases to test
- Only one stone
- Two equal stones (nothing left)
- All stones equal
- One stone much heavier than all others combined
Hints
Hint 1
At every turn you need the two largest values. Which data structure gives the maximum quickly and stays updated after insertions?
Hint 2
Use a max-heap: pop two, push back their difference if it is not zero.
FAQ
What is the best time complexity for Last Stone Weight?
Optimal (max-heap) runs in O(n log n) time and O(n) extra space. Each round removes at least one stone, so there are at most n rounds of O(log n) heap work.
Which pattern does Last Stone Weight use?
It is a heaps problem that uses the top k / kth largest / smallest pattern. Other problems with the same pattern: Kth Largest Element in an Array, Kth Largest Element in a Stream, Top K Frequent Words.
Is there a brute force solution for Last Stone Weight?
Yes. Brute force (sort every round) takes O(n² log n) time and O(n) space. Keep the stones in a list.
Which edge cases should I test for Last Stone Weight?
Only one stone; Two equal stones (nothing left); All stones equal; One stone much heavier than all others combined.