Problem Statement

You are given an integer array asteroids of size n, where asteroids[i] represents the size and direction of the i^th asteroid.

The size of an asteroid is represented by the absolute value of asteroids[i], and its direction is indicated by the integer's sign: positive for rightward and negative for leftward. Each asteroid moves at the same speed.

When two asteroids collide, the smaller one shatters. If they are of equal size, both are destroyed. Asteroids moving in the same direction never collide.

Return the final state of asteroids after all possible collisions have been resolved.

Examples

• Example 1:

  • Input: asteroids = [8, -3, 4, -5]
  • Expected Output: [8]
  • Justification: The asteroid 4 collides with -5, and since -5 is larger, 4 is destroyed. Next, -3 and -5 get destroyed when they collide with 8.

• Example 2:

  • Input: asteroids = [-2, -1, 1, 2]
  • Expected Output: [-2, -1, 1, 2]
  • Justification: Since the asteroids are moving in opposite directions, there are no collisions.

• Example 3:

  • Input: asteroids = [5, -3, 8, -2, -4, 1, -1]
  • Expected Output: [5, 8]
  • Justification: The sequence of interactions is as follows:
    • 5 and -3 collide, and -3 will get destroyed.
    • 8 and -2 collide, and -2 will get destroyed.
    • -4 will be destroyed after collision with 8.
    • 1 and -1 collide and both are destroyed because they have the same magnitude but opposite directions.
    • The final configuration is [5, 8], as these asteroids survive without further collisions.

Constraints:

• 2 <= asteroids.length <= 10⁴
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

Solution

To solve this problem, we'll use a stack to keep track of the asteroids. This approach works because the problem inherently deals with a sequence of elements where the most recent element might only interact with the one directly before it, which is a perfect scenario for a stack.

When an asteroid moves right (positive), we push it onto the stack. When an asteroid moves left (negative), we compare it with the top of the stack. If the top is moving right, we determine the outcome of the collision. If the asteroid moving left survives, we continue comparing it with the new top of the stack until it either destroys all opposing asteroids or is destroyed itself. This method ensures we only keep asteroids that have survived all possible collisions, effectively simulating the process described in the problem.

Step-by-Step Algorithm

1. Initialize a Stack: Create an empty stack to keep track of the asteroids that are moving or have the potential to cause collisions.

2. Iterate Through Asteroids: Loop through each asteroid in the given array.

   • For each asteroid, check if it is moving left (negative value) and if there are any asteroids in the stack moving right (positive value at the top of the stack).

3. Handle Collisions:

   • If the current asteroid is moving left and the top of the stack is moving right, a collision might occur. Enter a while loop to handle this potential collision.
     • Destroy Bigger Asteroid: Compare the absolute values of the current asteroid and the one at the top of the stack. If the current asteroid is larger, pop the top of the stack (the right-moving asteroid is destroyed), and continue to the next iteration to check for more potential collisions.
     • Equal Size Destruction: If the asteroids are of equal size, pop the top of the stack and set the current asteroid to 0 (indicating it has been handled), then break out of the while loop since both asteroids destroy each other.
     • Smaller Asteroid Destroyed: If the current asteroid is smaller, simply set it to 0 (indicating it has been handled) and break out of the while loop.

4. Stack Update:

   • After handling collisions, if the current asteroid is not set to 0 (indicating it has survived or is moving right without any opposing asteroids), push it onto the stack.

5. Convert Stack to List:

   • Once all asteroids have been processed, convert the stack to a list to represent the final state of the asteroid field.

Algorithm Walkthrough

Input: asteroids = [5, -3, 8, -2, -4, 1, -1]

1. Start with an empty stack: []

2. Process 5:

   • 5 is moving right, no asteroids to collide with.
   • Stack after processing 5: [5]

3. Process -3:

   • -3 is moving left and encounters 5 moving right.
   • Since 3 is smaller than 5, -3 is destroyed.
   • Stack remains unchanged: [5]

4. Process 8:

   • 8 is moving right, no asteroids to collide with.
   • Stack after processing 8: [5, 8]

5. Process -2:

   • -2 is moving left and encounters 8 moving right.
   • Since 2 is smaller than 8, -2 is destroyed.
   • Stack remains unchanged: [5, 8]

6. Process -4:

   • -4 is moving left and encounters 8 moving right.
   • Since 4 is smaller than 8, -4 is destroyed.
   • Stack remains unchanged: [5, 8]

7. Process 1:

   • 1 is moving right, no immediate collision as the last asteroid (8) is also moving right.
   • Stack after processing 1: [5, 8, 1]

8. Process -1:

   • -1 is moving left and encounters 1 moving right.
   • Since -1 and 1 are of equal size, both are destroyed.
   • Stack after processing -1 (removing 1): [5, 8]

9. Final State:

   • The final configuration of the asteroid field is represented by the stack: [5, 8]

Code