Asteroid Collision

Medium

Problem

Asteroids move along a line: the absolute value is the size and the sign is the direction (+ right, − left). When two meet, the smaller one explodes, and if they are the same size both explode. Asteroids moving the same way never meet. Return the state after all collisions.

Example 1

Input:  [5, 10, -5]
Output: [5, 10]

Example 2

Input:  [8, -8]
Output: []

Example 3

Input:  [10, 2, -5]
Output: [10]

Test cases

Case 1

Input:    [5,10,-5]
Expected: [5,10]

Case 2

Input:    [8,-8]
Expected: []

Case 3

Input:    [10,2,-5]
Expected: [10]

Case 4

Input:    [-2,-1,1,2]
Expected: [-2,-1,1,2]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Stack of survivors

Time O(n)Space O(n)

Only a left-moving asteroid meeting a right-moving one on the stack collides. Pop smaller ones; destroy both on a tie.

function asteroidCollision(asteroids) {
const st = [];
for (const a of asteroids) {
let alive = true;
while (alive && a < 0 && st.length && st[st.length - 1] > 0) {
const top = st[st.length - 1];
if (top < -a) st.pop();
else { if (top === -a) st.pop(); alive = false; }
}
if (alive) st.push(a);
}
return st;
}