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
- 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
#include <algorithm>
#include <optional>
#include <utility>
#include <string>
#include <vector>
using namespace std;
vector<int> solve(const vector<int>& values) {
vector<int> stack;
for (int current : values) {
bool alive = true;
while (alive && current < 0 && !stack.empty() && stack.back() > 0) {
if (stack.back() < -1LL * current) stack.pop_back();
else {
if (stack.back() == -1LL * current) stack.pop_back();
alive = false;
}
}
if (alive) stack.push_back(current);
}
return stack;
}