We are given an array asteroids of integers representing asteroids in a row. The indices of the asteriod in the array represent their relative position in space.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

Example 3:

Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Let’s solve “Asteroid Collision” in your structured format — step-by-step, clean, and optimized for interviews.

✅ 1. Problem Explanation (In Simple Terms)

You're given an array of integers representing asteroids moving in space. The value represents:

Magnitude = size of the asteroid
Sign:
- Positive (+) = moving right
- Negative (-) = moving left

💥 When two asteroids collide:

The smaller one explodes.
If equal in size, both explode.
Only asteroids moving in opposite directions can collide (i.e., + meets -).

You need to simulate all collisions and return the final state of the asteroid field.

💡 2. Key Insights

Use a stack to simulate the sequence of asteroid collisions.
Only worry about collision when a right-moving asteroid (+) is followed by a left-moving asteroid (-).
When processing each asteroid:
- If it's moving right → just push to stack.
- If it's moving left:
  - Keep checking top of stack for right-moving asteroids
  - Resolve collision by comparing sizes
  - Remove exploded asteroids from the stack
Continue until no more collisions are possible.

🧠 3. Steps to Solve

Initialize an empty stack.
Iterate through each asteroid:
- If moving right → push to stack.
- If moving left:
  - While top of stack is right-moving and smaller than this:
    - Pop the right-moving one (it explodes)
  - If top is same size → both explode
  - If top is larger → current one explodes
  - If no collision → push to stack
Return the final stack after processing all asteroids.

✅ 4. JavaScript Code (Well-Commented)

/**
 * @param {number[]} asteroids
 * @return {number[]}
 */
function asteroidCollision(asteroids) {
  const stack = [];

  for (const asteroid of asteroids) {
    let destroyed = false;

    // Process left-moving asteroid
    while (
      stack.length > 0 &&
      stack[stack.length - 1] > 0 && // top is moving right
      asteroid < 0                  // current is moving left
    ) {
      const top = stack[stack.length - 1];

      if (Math.abs(asteroid) > top) {
        stack.pop(); // smaller right-moving asteroid destroyed
        continue;
      } else if (Math.abs(asteroid) === top) {
        stack.pop(); // both destroyed
        destroyed = true;
        break;
      } else {
        destroyed = true; // left-moving asteroid destroyed
        break;
      }
    }

    if (!destroyed) {
      stack.push(asteroid); // no collision or survived
    }
  }

  return stack;
}

🔍 5. Dry Run Example

Input: [5, 10, -5]

Stack: []

→ 5 → push → [5]  
→ 10 → push → [5, 10]  
→ -5 → check collisions with top (10)

- 10 > 5 → -5 destroyed → result: [5, 10]
✅ Output: [5, 10]

Another case:

Input: [8, -8]

→ 8 → push → [8]  
→ -8 → same size → both explode → []

✅ Output: []

⏱️ 6. Time & Space Complexity

Let n be the number of asteroids.

Time Complexity: O(n)
Each asteroid is pushed and popped at most once.
Space Complexity: O(n)
In the worst case (no collisions), all asteroids are stored in the stack.

✅ Final Verdict

This is a classic stack simulation problem.
Great candidate for interviews!
Fast and memory-efficient.

Asteroid Collision