How do you approach Last Stone Weight?

Each turn you need the two largest remaining values - repeatedly sorting works but is wasteful.

What is the time complexity of Last Stone Weight?

Time complexity: O(n log n) - each smash does O(log n) heap work. Space complexity: O(n) for the heap.

What are common mistakes on Last Stone Weight?

Using a max-heap for a k-largest question. The size-k min-heap is what turns O(n log n) into O(n log k). An inverted comparator, which is silent: the code runs and returns confidently wrong answers. Re-heapifying inside the loop instead of once up front.

gitGood.dev

← Back to problems

Last Stone Weight

EasyData Structures

Description

You are given an array of integers stones where stones[i] is the weight of the i-th stone.

On each turn, choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y:

If x == y, both stones are destroyed.
If x != y, the stone of weight x is destroyed, and the stone of weight y now has weight y - x.

At the end of the game, there is at most one stone left. Return the weight of the last remaining stone, or 0 if there are no stones left.

Example 1

Input: stones = [2,7,4,1,8,1]

Output: 1

Explanation: Smash 8 and 7 -> 1. Smash 4 and 2 -> 2. Smash 2 and 1 -> 1. Smash 1 and 1 -> 0. One stone of weight 1 remains.

Example 2

Input: stones = [1]

Output: 1

Example 3

Input: stones = [3,3]

Output: 0

Constraints

- 1 <= stones.length <= 30 - 1 <= stones[i] <= 1000

Last Stone Weight: approach, complexity and pitfalls

An easy heap / priority queue problem, graded against 6 test cases (3 of them hidden).

The pattern: Heap / Priority Queue

A priority queue for "top k" and streaming-median questions.

Reach for it when you see: "Top/smallest k", a running median, or repeatedly needing the current minimum.

More Heap / Priority Queue problems →

If you are stuck

Show the 3-step hint ladder

Each turn you need the two largest remaining values - repeatedly sorting works but is wasteful.
A max-heap (priority queue) gives you the largest element in O(log n) per operation.
Pop the two heaviest stones; if they differ, push the difference back. Repeat until at most one stone remains.

The optimal approach

Show the approach: Max-Heap

Put all stones in a max-heap. Repeatedly pop the two heaviest, and if they differ, push back the difference. When at most one stone remains, that's the answer (0 if none).

The reference solution hand-rolls a small array-based binary max-heap with `push` (sift up) and `pop` (sift down), so it needs no imports or libraries in either language.

Time: O(n log n) - each smash does O(log n) heap work
Space: O(n) for the heap

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Heap / Priority Queue mistakes

These apply to the pattern as a whole, not just this problem.

Using a max-heap for a k-largest question. The size-k min-heap is what turns O(n log n) into O(n log k).
An inverted comparator, which is silent: the code runs and returns confidently wrong answers.
Re-heapifying inside the loop instead of once up front.

← Back to problems

Last Stone Weight

EasyData Structures

Description

You are given an array of integers stones where stones[i] is the weight of the i-th stone.

On each turn, choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y:

If x == y, both stones are destroyed.
If x != y, the stone of weight x is destroyed, and the stone of weight y now has weight y - x.

At the end of the game, there is at most one stone left. Return the weight of the last remaining stone, or 0 if there are no stones left.

Example 1

Input: stones = [2,7,4,1,8,1]

Output: 1

Explanation: Smash 8 and 7 -> 1. Smash 4 and 2 -> 2. Smash 2 and 1 -> 1. Smash 1 and 1 -> 0. One stone of weight 1 remains.

Example 2

Input: stones = [1]

Output: 1

Example 3

Input: stones = [3,3]

Output: 0

Constraints

- 1 <= stones.length <= 30 - 1 <= stones[i] <= 1000

Last Stone Weight: approach, complexity and pitfalls

An easy heap / priority queue problem, graded against 6 test cases (3 of them hidden).

The pattern: Heap / Priority Queue

A priority queue for "top k" and streaming-median questions.

Reach for it when you see: "Top/smallest k", a running median, or repeatedly needing the current minimum.

More Heap / Priority Queue problems →

If you are stuck

Show the 3-step hint ladder

Each turn you need the two largest remaining values - repeatedly sorting works but is wasteful.
A max-heap (priority queue) gives you the largest element in O(log n) per operation.
Pop the two heaviest stones; if they differ, push the difference back. Repeat until at most one stone remains.

The optimal approach

Show the approach: Max-Heap

Put all stones in a max-heap. Repeatedly pop the two heaviest, and if they differ, push back the difference. When at most one stone remains, that's the answer (0 if none).

The reference solution hand-rolls a small array-based binary max-heap with `push` (sift up) and `pop` (sift down), so it needs no imports or libraries in either language.

Time: O(n log n) - each smash does O(log n) heap work
Space: O(n) for the heap

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Heap / Priority Queue mistakes

These apply to the pattern as a whole, not just this problem.

Using a max-heap for a k-largest question. The size-k min-heap is what turns O(n log n) into O(n log k).
An inverted comparator, which is silent: the code runs and returns confidently wrong answers.
Re-heapifying inside the loop instead of once up front.