← DSA Atlas
Dedicated problem page · #1046

Last Stone Weight

EasyHeap and Priority QueueRepeatedly combine two extremesMax-heap simulation
Solve on LeetCode ↗
1046
EasyHeap and Priority QueueMax-heap simulationRepeatedly combine two extremes

Last Stone Weight

Given an array stones where each value is a stone's weight, repeatedly take the two heaviest stones x <= y and smash them: if x == y both are destroyed, otherwise the heavier is destroyed and a stone of weight y - x remains. Continue until at most one stone is left; return its weight, or 0 if none remain.

Open official problem prompt ↗
In plain English

Simulate the smashing process by always combining the two currently heaviest stones and report what survives.

Picture it like this

A knockout tournament where the two strongest remaining fighters clash each round; if they tie both are out, otherwise the survivor re-enters with strength reduced by the loser's, and you ask who is left standing.

Example
Input
stones = [2, 7, 4, 1, 8, 1]
Output
1
Why
Smash 8&7 -> 1; 4&2 -> 2; 2&1 -> 1; 1&1 -> 0; the single stone left weighs 1.
Constraints
1 <= stones.length <= 301 <= stones[i] <= 1000
Pattern lesson

See the pattern, then code

Repeatedly combine two extremes
Recognition clue

Each step needs the two largest current values and puts a derived value back into the pool. Repeated extraction of maxima with reinsertion is the hallmark of a max-heap.

↗
Heap and Priority Queue

Top k, kth value, repeated minimum extraction, scheduling, or merging sorted streams.. You never need the whole sorted order, only the two biggest at any moment. A max-heap gives both in logarithmic time, and the difference (if nonzero) is pushed back to continue the simulation.

New words, made simpleKnow these before the algorithm
Max-heap
A heap exposing the largest element first; in Python built by negating values in a min-heap.
heapify
Turning an arbitrary list into a valid heap in O(n) time, in place.
Simulation
Directly enacting the described process step by step rather than deriving a closed formula.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Sort every round

Re-sorting after every smash is redundant work.

Re-sort the list each turn to find the two largest, smash, repeat.

Time O(n^2 log n)Space O(n)
Best choiceMax-heap simulation

Each of at most n rounds costs only logarithmic time.

Pop the two largest in O(log n) each, push back the difference, until one stone remains.

Time O(n log n)Space O(n)
The rule we keep true

Invariant

The heap always contains exactly the stones not yet destroyed, so its two pops each round are genuinely the two heaviest stones currently in play.

Why this is correct

Reasoning

The process is fully determined by picking the two heaviest stones each step, and a max-heap returns precisely those in order. Pushing back y - x (only when positive) reflects the surviving stone; when y == x nothing is pushed, correctly destroying both. The loop ends when fewer than two stones remain, matching the problem's stopping rule.

The algorithm in three movesSay these aloud before coding
1Build a max-heap of all stone weights

heap max = [8,7,...]

2While more than one stone remains, pop the two heaviest y and x

8-7 = 1 pushed

3If they differ, push y - x back onto the heap

... -> final stone 1

4When one or zero stones remain, return the last weight or 0

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
80
71
42
23
14
15
1 · Read[2,7,4,1,8,1]
2 · AskHeapify as max-heap
3 · Update statenegated heap, max = 8
4 · Result8 and 7 are the top two
Key takeaway

The two heaviest stones (8 and 7) are smashed first, leaving a stone of weight 1.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 5-6Negate and heapify

    Negate every weight so Python's min-heap behaves as a max-heap, then heapify in O(n).

  2. 2
    Lines 7-9Take the two heaviest

    While at least two stones remain, pop twice and un-negate to recover the real weights y (heaviest) and x.

  3. 3
    Lines 10-11Push the remnant

    If the weights differ, the surviving stone y - x re-enters the heap (negated); equal weights leave nothing behind.

  4. 4
    Lines 12Report survivor

    Return the last stone's weight, or 0 when the heap is empty.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • a single stone (returned unchanged)
  • two equal stones that annihilate to 0
  • all stones equal
  • the last two stones equal, leaving zero
!

Common beginner mistakes

  • Forgetting to negate consistently on both push and pop, corrupting the max-heap behavior
  • Pushing 0 back onto the heap when y == x instead of pushing nothing
  • Popping when only one stone is left (loop guard must require size > 1)
  • Returning heap[0] without un-negating it or without the empty-heap guard
Check your understanding

Why is a max-heap preferable to sorting the list on each smash?

More in Heap and Priority Queue

#215Kth Largest Element in an ArrayBounded min-heap of size k#295Find Median from Data StreamTwo balanced heaps#373Find K Pairs with Smallest Sumsk-way merge with a heap#502IPOGreedy with a max-heap of affordable options#621Task SchedulerFill idle slots around the most frequent task#692Top K Frequent WordsCount then heap-order by frequency and word