Asteroid Collision
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]
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;}