Workspace

Problem workspace

3 day streakD

Asteroid Collision

MediumStacksSimulation & greedy

The challenge

Return surviving asteroids after every possible collision. Sign gives direction; magnitude gives size.

Nonzero signed integers. Asteroids move at equal speed; equal sizes destroy both.

Example

[5,10,-5] → [5,10]; [8,-8] → [].

Use the walkthrough below to inspect the input and each state change.

See Asteroid Collision, step by step

Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.

Zero-based input · top labeled explicitlyLIFO
Input and stack stateCurrent input index: -1. Main stack bottom to top: []. Auxiliary stack · bottom → top: []. Read the input in order. The stack keeps only the state needed to resolve the next item.50101-52Main stack · bottom → top ↑emptyAuxiliary · bottom → top ↑empty
Current input index
—
Main stack size
0
Step 01 / 6

Start with an empty stack

Read the input in order. The stack keeps only the state needed to resolve the next item.

Answer so far

Not recorded yet
Main stack · bottom → top
Empty
Auxiliary stack · bottom → top
Empty
View exact input and state

Input: [5,10,-5]

Main stack: []. Auxiliary stack · bottom → top: [].

Put it into code

While top > 0 and current < 0, destroy the smaller magnitude.

Indices are zero-based. C++ uses C++17 or later.

def solve(values):
    stack = []
    for current in values:
        alive = True
        while alive and current < 0 and stack and stack[-1] > 0:
            if stack[-1] < -current: stack.pop()
            else:
                if stack[-1] == -current: stack.pop()
                alive = False
        if alive: stack.append(current)
    return stack

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap