Last Stone Weight

Table of Contents +

You have a pile of stones. Each round you smash the two heaviest together. They cancel out, sometimes leaving a smaller stone. You repeat until one stone or none is left. The job is to find the weight of that last stone. The trick is always grabbing the two heaviest fast. That is a perfect job for a heap.

🎯 The Problem

You get a list of stone weights, and each turn you smash the two heaviest stones together.

The smash rules:

  • If the two stones weigh the same, both are gone.
  • If they differ, the smaller one is gone and the heavier one shrinks to the difference.

The goal:

  • Keep smashing until one stone is left or none.
  • Return the weight of the last stone.
  • If no stones are left, return 0.
Input:  stones = [2, 7, 4, 1, 8, 1]
Output: 1


Explanation:
smash 8 and 7 -> 1 left, stones = [2, 4, 1, 1, 1]
smash 4 and 2 -> 2 left, stones = [2, 1, 1, 1]
smash 2 and 1 -> 1 left, stones = [1, 1, 1]
smash 1 and 1 -> 0 left, stones = [1]
one stone left -> answer = 1

So we always need the two heaviest. After a smash, a new weight may join back in. Then we need the two heaviest again.

Here is the smashing process drawn as a flow.

Yes

No

Yes

No

Pile of stones

Take two heaviest

Equal weight?

Both gone

Put back the difference

More than one stone?

Return last weight or 0

🐢 Approach 1: Sort Every Round (Brute Force)

The idea in one line: keep the list sorted and re-sort after each smash.

The idea:

  • Keep the list sorted.
  • Each round, take the last two values. Those are the heaviest.
  • Smash them. If a difference is left, insert it back in the right spot.
  • Re-sort for the next round.

Why it is weak:

  • Sorting again every round is wasteful.
  • Each sort is O(n log n), and you may run many rounds.
  • You pay a full sort just to find two values.

Here is the sort-every-round code:

last_stone_weight_sort_each_round.py
def last_stone_weight(stones):
    while len(stones) > 1:
        stones.sort()
        y = stones.pop()
        x = stones.pop()
        if x != y:
            stones.append(y - x)
    return stones[0] if stones else 0

⚡ Approach 2: A Max-Heap (Best)

The idea in one line: keep the two heaviest stones ready at the top with a heap.

What a max-heap is:

  • A max-heap is a binary tree kept in an array with the largest value at the top.
  • Reading the top is instant. Adding or removing is O(log n). It is also called a priority queue.

How it works:

  • Put all stones into a max-heap.
  • Each round, pop the top twice. Those are the two heaviest.
  • Smash them. If a positive difference is left, push it back.
  • Keep going while the heap has more than one stone.
  • At the end, return the last stone’s weight, or 0 if the heap is empty.

Why it is fast:

  • Each pop or push is O(log n).
  • The heap fixes its order each time, so you never re-sort the whole pile.

Here is the max-heap drawn as a tree for the starting pile. The heaviest stone, 8, sits at the top, ready to be smashed first.

8

7

4

1

2

1

Steps to Solve

  1. Put all stone weights into a max-heap.
  2. While the heap has more than one stone, pop the two heaviest.
  3. If they differ, push the difference back onto the heap.
  4. If they are equal, both vanish, so push nothing.
  5. When one stone is left, return its weight. If none are left, return 0.

Python’s heapq gives a min-heap. To get a max-heap we negate every value, so the most negative sits on top, which is the largest original number.

last_stone.py
import heapq




def last_stone_weight(stones):
    heap = [-s for s in stones]   # negate to make a max-heap
    heapq.heapify(heap)           # build the heap in O(n)
    while len(heap) > 1:
        a = -heapq.heappop(heap)  # heaviest
        b = -heapq.heappop(heap)  # second heaviest
        if a != b:
            heapq.heappush(heap, -(a - b))  # push the difference back
    return -heap[0] if heap else 0




stones = [2, 7, 4, 1, 8, 1]
print(last_stone_weight(stones))

The output of the above code will be:

1

Let us walk through the Python version line by line. Python only gives a min-heap, so we work around that.

The first line builds a new list with every value negated. So a stone of 8 becomes -8. The most negative value is now the largest original number. The second line calls heapq.heapify. This turns the list into a valid heap in O(n), which is faster than pushing one by one.

The while runs while two or more stones remain. Inside, we pop twice. Each pop gives the most negative value, so we negate it back to get the real weight. The first pop is the heaviest stone. The second pop is the next heaviest.

The if a != b checks if the two stones differ. If they do, one stone survives with weight a - b. We push it back, negated again, so the heap stays a max-heap. If they are equal, both vanish and we push nothing.

When the loop ends, at most one stone remains. The last line returns -heap[0] if the heap is not empty, undoing the negation. If the heap is empty, it returns 0.

⏱️ Time and Space Complexity

The repeated-sort approach pays a full sort each round. The max-heap approach pays only O(log n) per pop or push. We run about n rounds, each doing a constant number of heap operations. So the total is O(n log n), but it is steady and avoids re-sorting the whole pile. Space is O(n) to hold the stones in the heap.

Approach Time Complexity Space Complexity
Sort every round O(n² log n) O(n)
Max-heap O(n log n) O(n)

Tip

Any problem that repeats “grab the biggest” or “grab the smallest” again and again is a heap problem. The heap keeps the extreme value ready, so you never re-scan or re-sort.

🧩 Key Takeaways

  • ✅ A max-heap keeps the largest value at the top, so the two heaviest are always ready.
  • ✅ Each round you pop two, smash them, and push back the difference if any.
  • ✅ Each pop and push is O(log n), so you avoid re-sorting the whole pile.
  • ✅ In Python, negate values to turn the min-heap into a max-heap.
  • ✅ Return the last stone’s weight, or 0 if none are left.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    Why is a max-heap a good fit for this problem?

    Why: Each round needs the two heaviest stones, and a max-heap always has the largest value ready at the top.

  2. 2

    When two smashed stones differ, what goes back into the heap?

    Why: The lighter stone is destroyed and the heavier one shrinks to the difference, which is pushed back.

  3. 3

    How do you make a max-heap in Python, which only has a min-heap?

    Why: Pushing negated values makes the most negative sit on top, which is the largest original number.

  4. 4

    What is returned when the heap becomes empty?

    Why: If every stone canceled out, no stone is left, so the answer is 0.

Score: 0 / 4

🚀 What’s Next?

Previous Kth Largest Element in a Stream Next K Closest Points to Origin