LeetCode #1046 Easy

Last Stone Weight

Repeatedly smash the two heaviest stones together; equal weights destroy both, otherwise the difference remains. Return the weight of the last stone, or 0.

heapgreedyarray

Open on LeetCode ↗

02

Intuition

💡

The naive approach re-sorts the whole list after every smash just to find the new top two, which is O(n^2 log n) and throws away work the previous sort already did. The operation only ever needs the two largest values and feeds one value back in, which is a max-heap almost verbatim — pop twice, push the difference if non-zero, repeat until at most one stone remains. Python's heapq is min-heap only, so every weight has to go in negated, and it's easy to smash correctly but forget to negate the final answer back on the way out, returning a negative weight.

03

Approach

1

Match the data structure to the operation

Every round needs the two maxima and then inserts a new value. A sorted list gives O(n) insertion per round, while a heap gives O(log n) for both the pops and the push — the deciding factor once the number of rounds grows.

2

Negate for Python's min-heap

heapq is a min-heap only, so store negated weights and negate again on the way out. Alternatively use a language with a max-heap directly, but the negation trick is worth knowing because it comes up constantly in Python solutions.

3

Smash until one or none remains

While at least two stones are present, pop a and b (the two largest). If they differ, push a - b back. If they are equal, push nothing — both are destroyed. When the loop ends, return the single remaining stone or 0 for an empty heap. Building the heap is O(n) and each of at most n rounds costs O(log n), so the total is O(n log n) time and O(n) space.

04

Solution & live demo

python

▶1import heapq
▶2 
▶3class Solution:
▶4    def lastStoneWeight(self, stones):
▶5        heap = [-w for w in stones]
▶6        heapq.heapify(heap)
▶7        while len(heap) > 1:
▶8            a = -heapq.heappop(heap)
▶9            b = -heapq.heappop(heap)
▶10            if a != b:
▶11                heapq.heappush(heap, -(a - b))
▶12        return -heap[0] if heap else 0

05

Edge cases

Single stone

The loop never runs and that stone's weight is returned.

All stones equal, even count

They pair off and destroy each other completely, so the answer is 0.

All stones equal, odd count

One survives, so the answer is that weight.

Forgetting to negate on the way out

The answer comes back negative — the classic slip with the negated-heap trick.

06

Complexity

Time

O(n log n)

Space

O(n)

Heapify is O(n); each round is O(log n) and there are at most n rounds.