PPractick

The problem

A space game shows asteroids in a row. Each has a size (the absolute value) and a direction: a positive value moves right, a negative one moves left, all at the same speed. When a right-mover meets a left-mover, the smaller one explodes, and if they're equal both explode. Asteroids moving the same way never meet. Report the final state. A stack of survivors models it perfectly: only a new left-mover can hit the survivors, and only the right-movers at the top of the stack, one after another.

Example: [10, 2, -5] → [10] (−5 destroys 2, then 10 destroys −5).

Function signature

vector<int> asteroidCollision(const vector<int>& asteroids);  // no zeros

Test cases

Input	Output	Explanation
[5, 10, -5]	[5, 10]	10 destroys −5
[8, -8]	[]	Equal sizes: both explode
[10, 2, -5]	[10]	−5 beats 2, then loses to 10
[-2, -1, 1, 2]	[-2, -1, 1, 2]	Moving apart: no collisions
[1, -2, -2, -2]	[-2, -2, -2]

(Confirm: values are non-zero; all asteroids move at the same speed; the relative order of survivors is preserved.)

How interviewers phrase it

• "Given an array of integers representing asteroids in a row, find the state after all collisions" (LeetCode 735).

Clarifying questions to ask

1. Do a left-mover on the left and a right-mover on the right collide? (No, they move apart.)
2. What happens with equal sizes? (Both explode.)
3. Can a value be 0? (No.)

Follow-ups to expect

1. "Why a stack?"
2. "When does a collision happen?"
3. "What are the outcomes?"
4. "Why is it O(n)?"
5. "What does the final stack look like?"

Related questions

• Print the matrix in spiral manner Medium
• Remove Outermost Parentheses Medium
• Maximum Nesting Depth of the Parentheses Medium
• Sort a stack using recursion Medium
• Reverse a Stack Medium
• Infix to Postfix Conversion Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in