Abstract / Summary

Rocks moving left and right collide and explode when their sizes match, removing both from motion.

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 49% (2+ million submissions).

Typical patterns to solve this problem:

• Array
• Simulation
• Stack

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 provided implementation solves the classic asteroid collision problem by iterating through the input list once and maintaining a stack that represents the current state of surviving asteroids. Each asteroid is examined in order, and potential collisions are resolved immediately by comparing the top two elements of the stack. The algorithm relies on the sign of the integers to infer direction (positive moves right, negative moves left) and on absolute values to determine size. By performing all necessary checks while the stack is being built, the solution avoids a second pass and keeps auxiliary storage to a minimum.

Core Logic

Stack Initialization

The algorithm begins by creating an empty list that will serve as a stack. This stack holds asteroids that have not been destroyed up to the current point in the iteration.

stack = []

Main Traversal

A single for loop walks through each asteroid in the input sequence. Each asteroid is appended to the stack before any collision logic is applied. This ordering ensures that newly encountered asteroids are positioned at the top of the stack, ready for immediate comparison with the preceding element.

for a in asteroids:
    stack.append(a)
    # collision handling follows

Collision Detection Condition

Inside the loop, a while construct checks whether the top two asteroids on the stack are moving toward each other. The condition stack[-2] > stack[-1] guarantees that the left-most asteroid is moving right (positive) while the right-most is moving left (negative). Multiplying the two values and confirming a negative product (stack[-2] * stack[-1] < 0) reinforces that the directions are opposite. The loop continues as long as a collision is possible.

while len(stack) >= 2 and stack[-2] > stack[-1] and stack[-2] * stack[-1] < 0:
    # resolve the collision

Equal-Size Collision

When the absolute sizes of the two colliding asteroids match, both are removed from the stack. This is achieved by two consecutive pop operations, which discard the topmost asteroid and then the one beneath it.

if abs(stack[-2]) == abs(stack[-1]):
    stack.pop()   # both explode
    stack.pop()

Unequal-Size Collision

If the sizes differ, the smaller asteroid is eliminated while the larger one survives. The code distinguishes the case where the newer asteroid (the top of the stack) is larger; in that scenario the surviving asteroid’s value is copied into the second-top position before the top is popped. When the older asteroid is larger, only the top element is removed, leaving the older one untouched.

else:
    if abs(stack[-2]) < abs(stack[-1]):
        stack[-2] = stack[-1]
    stack.pop()

Final Result

After processing all input asteroids, the stack contains only those that have not been destroyed. The method returns this list directly.

return stack

Edge Cases Handled

The algorithm gracefully manages several subtle situations without additional branching. When an incoming asteroid collides with a chain of previously stored asteroids, the inner while loop repeatedly evaluates the top two elements, allowing a cascade of collisions to resolve in a single pass. The equal-size check ensures that a pair of asteroids of identical magnitude annihilate each other, leaving no residue on the stack. Additionally, the condition len(stack) >= 2 prevents out-of-range errors when the stack contains fewer than two elements, thereby handling the case where the first asteroid cannot collide with anything.

Performance Optimizations

The solution’s primary optimization stems from its use of a mutable stack that is updated in place. By overwriting the second-top element with the surviving asteroid’s value (stack[-2] = stack[-1]) when the newer asteroid is larger, the code avoids an extra push-pop cycle that would otherwise be required to reposition the survivor. This in-place replacement reduces the number of list operations and keeps the stack’s size as small as possible throughout execution. Moreover, the inner while loop terminates as soon as no further collisions are possible, preventing unnecessary comparisons once the current asteroid has either been destroyed or settled into a stable position. The overall design ensures that each asteroid is pushed onto the stack at most once and popped at most once, leading to an efficient traversal with minimal overhead.

Imagine a long row in space where shiny asteroids are floating along. Some move to the right and some move to the left. The code acts like a helper that watches these asteroids as they travel. It uses a special tray called a stack to keep track of which ones are still floating safely.

When a new asteroid comes along, it gets placed onto the tray. The code constantly checks the last two asteroids sitting on the tray to see if they are about to bump into each other. For a crash to happen, the one on the left must be moving right, and the one on the right must be moving left.

If they are heading toward each other, a dramatic space collision occurs. There are three ways a crash can end. Sometimes both asteroids are the same size, so they both shatter into tiny pieces and disappear from the tray. Other times, one is bigger than the other. The bigger one stays in space while the smaller one is destroyed and removed from the tray. If the newer one is much bigger, it replaces the spot of the smaller one before moving on. The code keeps checking these collisions until all the asteroids are moving in ways where they will never hit each other again.

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

Time: linear
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++	Python	Java								TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java			Rust			Go		TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	AdelDaniel										Dart
	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai			Java
	Dijkstra-Edu	C++
	everthis				JS
	fartem							Ruby
	fengvyi	C++
	fpdjsns	C++
	halfrost									Go
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007		Python
	ruoru						Rust
	suxrobGM					C#
	trung-hn		Python
	varunu28			Java
	vthwang			Java
	yuanliu666								Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
AdelDaniel	Dart
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
Dijkstra-Edu	C++
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fpdjsns	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
yuanliu666	Kotlin
YuriSpiridonov	Python
zfang399	C++

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