735. Asteroid Collision - Detailed Explanation

Problem Statement

Description:
You are given an integer array asteroids where each element represents an asteroid:

• The absolute value represents the size.
• The sign represents the direction: positive for rightward, negative for leftward.

When two asteroids collide:

• The smaller one (by absolute value) explodes.
• If both are of the same size, both explode.
• Asteroids moving in the same direction never collide.

Return an array representing the state of the asteroids after all collisions.

Example 1:

• Input: asteroids = [5, 10, -5]
• Output: [5, 10]
• Explanation:
  The asteroid 10 and -5 collide. Since 10 is larger than 5, the -5 explodes. Asteroid 5 never collides with 10.

Example 2:

• Input: asteroids = [8, -8]
• Output: []
• Explanation:
  The asteroid 8 and -8 collide and both explode because they are of equal size.

Example 3:

• Input: asteroids = [10, 2, -5]
• Output: [10]
• Explanation:
  Asteroid 2 and -5 collide resulting in -5 surviving (since 5 > 2) but then 10 and -5 collide and 10 survives.

Hints

• Hint 1:
  Think about how asteroids moving to the right might eventually encounter asteroids moving to the left. Collisions occur only when a right-moving asteroid is followed by a left-moving one.

• Hint 2:
  A stack is a natural data structure for this problem because you can "simulate" the collisions as you iterate through the array, comparing the current asteroid with the ones that have not yet collided (stored on the stack).

• Hint 3:
  When the current asteroid is moving left (a negative value), repeatedly check the top of the stack (which represents a previous right-moving asteroid) to resolve collisions. Continue this process until either the current asteroid is destroyed, no collision is possible, or you’ve resolved all collisions with right-moving asteroids.

Approach: Using a Stack to Simulate Collisions

Idea

1. Initialize an Empty Stack:
   Use a stack to keep track of asteroids that have not yet exploded. The stack will store asteroids in the order they appear after surviving collisions.

2. Iterate Through the Asteroids:

   • If the current asteroid is moving right (positive), push it onto the stack because it may later collide with an asteroid moving left.
   • If the current asteroid is moving left (negative), check the top of the stack:
     • While there is a right-moving asteroid on the top of the stack (positive) and collisions are possible:

       • Compare the sizes (absolute values).

       • If the top asteroid is smaller (absolute value) than the current one, pop the top asteroid (it explodes) and continue checking.

       • If the top asteroid is equal in size, pop it and do not push the current asteroid (both explode).

       • If the top asteroid is larger, the current asteroid explodes (do not push it) and stop checking.

   • If no collision occurs (or all right-moving asteroids have been popped), push the current asteroid onto the stack.

3. Return the Stack:
   After processing all asteroids, the stack will contain the surviving asteroids in order.

Why This Works

• The stack helps you "remember" the last right-moving asteroids that could collide with an incoming left-moving asteroid.
• By checking collisions in a loop, you can simulate the chain reaction where one collision leads to the possibility of another.

Code Implementation

Python Code