This problem follows the Max-Heap Simulation pattern, commonly found in the Heap / Priority Queue category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Use a max-heap. Pop two largest, push the difference if non-zero.
Python only has min-heaps — negate values to simulate a max-heap. The greedy approach of always smashing the two heaviest is provably optimal.
heap = [-s for s in stones] # negate for max-heap
heapify(heap)
while len(heap) > 1:
a = -heappop(heap)
b = -heappop(heap)
if a != b:
heappush(heap, -(a - b))
return -heap[0] if heap else 0Practice Last Stone Weight and similar Heap / Priority Queue problems with flashcards. Build pattern recognition through active recall.
Practice this problem