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

Try it yourself

Try solving this question here: