Abstract / Summary

Repeatedly smash the two heaviest stones together until at most one stone remains and output its weight.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 66% (900k+ submissions).

Typical patterns to solve this problem:

• Array
• Heap (Priority Queue)

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation solves the classic “last stone weight” problem by repeatedly smashing the two heaviest stones until at most one stone remains. It leverages Python’s heapq module, which provides a binary min-heap, and adapts it to behave as a max-heap through sign inversion. The algorithm proceeds in three logical phases: preparation of the heap, iterative reduction of the stone set, and extraction of the final result.

Conversion to Max-Heap

The first phase transforms the input list of positive integers into a structure that supports efficient retrieval of the largest element. Because heapq only implements a min-heap, each stone weight is negated in place. This in-place negation avoids allocating a secondary list and keeps memory usage minimal.

for i in range(len(stones)):
    stones[i] = -stones[i]
heapify(stones)

The heapify call builds the heap in linear time, arranging the negated values so that the smallest (most negative) element corresponds to the original largest stone. By performing the sign change directly on the original list, the code eliminates the need for an auxiliary array, which is a subtle performance optimization.

Main Loop

The core of the algorithm resides in a while loop that continues as long as more than one stone is present in the heap. In each iteration, the two smallest elements of the negated heap are popped, which correspond to the two largest original stones. The sign is restored immediately after extraction.

while len(stones) > 1:
    y = -heappop(stones)
    x = -heappop(stones)
    if x != y:
        heappush(stones, -(y - x))

The variables y and x hold the larger and smaller of the two selected stones, respectively, after the sign correction. If the stones have equal weight, both are discarded, mirroring the problem’s rule that equal stones annihilate each other. When the weights differ, the difference y - x represents the new stone that remains after the smash; this difference is negated again before being pushed back onto the heap, preserving the max-heap invariant.

The loop’s condition len(stones) > 1 naturally handles the case where the heap becomes empty after a pair of equal stones is removed, as the loop will terminate without attempting further pops.

Final Result

After the loop exits, at most one element may remain in the heap. The final return statement restores the original sign of the remaining stone, if any, or yields zero when the heap is empty.

return -stones[0] if stones else 0

This conditional expression elegantly covers two edge cases: an empty input list and a scenario where all stones have been eliminated through successive equal-weight collisions. In both situations, the function returns 0, which aligns with the expected output for an empty stone set.

Edge Cases Handled

The algorithm gracefully manages several boundary conditions without additional branching logic. When the input list is empty, the initial for loop performs no iterations, heapify receives an empty list, and the final conditional returns 0. A single-stone input bypasses the while loop entirely, and the return statement yields the original stone weight after sign correction. When all stones have identical weight, each pair is removed in the loop, eventually emptying the heap and causing the function to return 0. The use of sign inversion ensures that the heap operations remain valid even when the list contains duplicate values.

Performance Optimizations

The code exhibits a few deliberate choices aimed at reducing overhead. Converting the list to a max-heap via in-place negation avoids the cost of constructing a new list, thereby saving both time and memory. The single call to heapify builds the heap in linear time, which is more efficient than inserting each element individually with heappush. Within the loop, the algorithm only pushes a new element when a non-zero difference arises, preventing unnecessary heap insertions for equal stones. The conditional return that checks the heap’s emptiness eliminates the need for an extra length check after the loop, streamlining the final step. These decisions collectively contribute to a concise and efficient solution.

Imagine a playground where heavy rocks are waiting to have a contest. First, the rocks are labeled with numbers that show how big and heavy they are. To make the computer work with the heaviest rocks first, the code turns every number into a negative one. This is like a special trick that helps the computer find the biggest rock super fast.

Next, the code starts a game that keeps going as long as there are at least two rocks left in the pile. Two of the biggest rocks are pulled out to fight. If one rock is bigger than the other, the smaller one is smashed into dust and the bigger one loses a little bit of its weight. That bigger rock is then put back into the pile to wait for another turn. If both rocks are exactly the same size, they both smash each other into tiny pieces and disappear forever. This game continues until there is either one rock left or no rocks at all.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python								TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python	JS						Go	TS
	LeetcodeHelp	C++	Java	Python
	MemoryLimitExceeded	C++		Python
	Progiez	C++	Java	Python
github	aylei						Rust
	BigEggStudy					C#
	black-shadows	C++
	bujosa			Python
	charles-wangkai		Java
	Dijkstra-Edu		Java
	DimitrisJim									C
	everthis				JS
	fartem							Ruby
	FelixFan1122		Java
	fpdjsns	C++
	fsq	C++
	Garvit244			Python
	JoshCrozier				JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007			Python
	sonugiri1043	C++
	suxrobGM					C#
	varunu28		Java
	vthwang		Java
	yuanliu666								Kotlin
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
charles-wangkai	Java
Dijkstra-Edu	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	Java
fpdjsns	C++
fsq	C++
Garvit244	Python
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vthwang	Java
yuanliu666	Kotlin

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality