Free lessonsHeaps · Stage 0 · Smallest first · Step 3

Last stone weight

Repeatedly smash the two heaviest stones using a max-heap until at most one remains. About 8 minutes.

The stone collision game

You have a pile of stones. On each turn, you pick the two heaviest and smash them together. If they weigh the same, both are destroyed. If not, the lighter one is destroyed and the heavier one loses as much weight as the lighter one had.

Keep going until at most one stone is left.

Always heaviest: the two largest stones collide first.

Reinsert the leftover: if any weight remains, put it back in the heap.

stones in a max-heap (heaviest first)

left: 6

The two heaviest: 8 and 7. They smash; 8 − 7 = 1 survives.

Move 1 of 5

Using a Max-Heap

A max-heap keeps the largest element at the top. In C++, the priority queue is a max-heap by default. In Java, give the PriorityQueue a reverse-order comparison. In Python, which only has a min-heap, store each number as its negative, so the largest becomes the smallest.

Just remember to flip the sign again when you take a number out.

C++: the priority queue is a max-heap by default.

Java: pass a reverse-order comparison to the PriorityQueue.

Python trick: negate numbers so the largest becomes the smallest.

In code

import heapq

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 0

Quick check

You have stones [2, 7, 4, 1, 8, 1]. What are the first two stones smashed?

A8 and 7
B2 and 7
C1 and 1

Show the answer

8 and 7. 8 and 7 are the two heaviest stones in the collection.

Your problem

Last stone weight

You are given an array of integers stones where stones[i] is the weight of the i-th stone. We play a game with the stones. On each turn, we choose the heaviest two stones 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 has new 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

stones = [2, 7, 4, 1, 8, 1] → 1

1 ≤ stones.length ≤ 100,000 · 1 ≤ stones[i] ≤ 100,000

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.

Start coding