4.17.2 — Last Stone Weight

LeetCode 1046 · Easy

The problem

Repeatedly take the two heaviest stones and smash them together. If they weigh the same, both are destroyed. If not, the heavier one is left with the difference. Return the weight of the last stone, or 0 if none remain.

[2, 7, 4, 1, 8, 1]

8 and 7 → 1 left        [2, 4, 1, 1, 1]
4 and 2 → 2 left        [2, 1, 1, 1]
2 and 1 → 1 left        [1, 1, 1]
1 and 1 → both gone     [1]
→ 1

The pattern

The operation is always "give me the two largest", repeated. A structure that hands you the largest in O(\log n) and takes back a new value just as cheaply is a max-heap.

Sorting the array once does not work, because the leftover stone has a new weight and must be reinserted in order. You would re-sort after every smash, which is O(n^2 \log n).

The Python trick for a max-heap

heapq only gives you a min-heap. To get a max-heap, negate every value on the way in and on the way out.

heap = [-s for s in stones]      # negate
heapq.heapify(heap)
largest = -heapq.heappop(heap)   # negate back

The smallest negative number is the largest original, so a min-heap over negatives behaves as a max-heap.

Remember to negate on the way out. Forgetting is the standard bug, and it produces negative answers that look obviously wrong — which is at least a fast failure.

The solution

Python

import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        heap = [-s for s in stones]
        heapq.heapify(heap)                      # O(n)

        while len(heap) > 1:
            first = -heapq.heappop(heap)         # largest
            second = -heapq.heappop(heap)        # second largest
            if first != second:
                heapq.heappush(heap, -(first - second))

        return -heap[0] if heap else 0

TypeScript

// assumes a MaxHeap with push, pop, size, peek
function lastStoneWeight(stones: number[]): number {
  const heap = new MaxHeap<number>();
  for (const s of stones) heap.push(s);

  while (heap.size > 1) {
    const first = heap.pop()!;
    const second = heap.pop()!;
    if (first !== second) heap.push(first - second);
  }

  return heap.size ? heap.peek()! : 0;
}

The loop condition is > 1, not > 0. A smash needs two stones; one stone alone is the answer.

Nothing is pushed when the two are equal, because both stones are destroyed.

first >= second always, since the first pop gives the larger, so the difference is never negative and needs no abs.

Complexity

O(n \log n). Each smash removes at least one stone, so there are at most n rounds, and each does a constant number of O(\log n) heap operations.

O(n) space.

The bounded-values alternative

The constraints say stone weights are at most 1,000. When values are small and bounded, counting beats a heap — the same realisation as bucket sort in 4.4.5.

Keep an array of 1,001 counts and scan downwards for the two largest. Each scan is O(1001), a constant, so the total is O(n) with a large constant factor.

On these inputs the heap is faster in practice, because n is at most 30 and the constant on a 1,001-slot scan is much worse. The point is not that counting wins here — it is that you noticed the values were bounded and considered it. That habit is what makes the linear solutions in other problems findable.

Where this goes next

• Minimum Cost to Connect Sticks — repeatedly combine the two smallest, and the total cost is the sum of the combinations. A min-heap, and it is exactly how Huffman coding builds its tree (Chapter 1.8).
• Reorganize String and Task Scheduler — repeatedly take the most frequent item. 4.17.5.
• Any greedy simulation where each step needs the current extreme.

The rule: when a loop repeatedly needs the largest or smallest of a changing collection, that is a heap. Sorting only works when the collection stops changing.

What the interviewer will push on

"Why not just sort?" The leftover stone has a new weight and must be reinserted in order, so you would re-sort every round.

"How do you get a max-heap in Python?" Negate on the way in and out.

"Why is the loop condition > 1?" A smash needs two stones.

"The weights are bounded — does that change anything?" Counting is possible, and say honestly why it does not help at n = 30.

One thing to volunteer: name Huffman coding when you mention the smallest-two variant. It shows the pattern is something you recognise rather than a one-off.

Next: 4.17.3 K Closest Points to Origin — a size-k heap again, but the other way round.