Destroying Asteroids - Leetcode Solution

The Destroying Asteroids problem on LeetCode is a problem that requires you to simulate a given scenario in which asteroids are moving towards each other, and you need to destroy them in a way that only the largest one survives. The solution to this problem can be broken down into the following steps:

1. Initialization - Initialize an empty stack that will keep track of all the asteroids that have not been destroyed yet.

2. Iterate over the list of given asteroids, and for each asteroid, perform the following steps:

   a. If the size of the asteroid is positive, add it to the stack.

   b. If the size of the asteroid is negative (meaning it is moving towards the left), loop until there are either no more asteroids in the stack or the size of the asteroid in the top of the stack is smaller than or equal to the absolute value of the current asteroid's size.

   c. If there are no asteroids left in the stack, add the current asteroid to the stack.

   d. If the asteroid in the top of the stack is equal in size to the absolute value of the current asteroid, pop the asteroid from the stack and do not add the current asteroid.

   e. If the asteroid in the top of the stack is smaller in size than the absolute value of the current asteroid, pop the asteroid from the stack, and continue with the next step in the loop.

3. Return the asteroids in the stack as the final result.

The algorithm works by keeping track of a stack of asteroids that have not been destroyed yet. When a positive asteroid is encountered, it is added to the stack, since it will not collide with any prior asteroids. However, if a negative asteroid is encountered, it means that it will collide with the next positive asteroid(s) that it encounters. If the top asteroid in the stack is larger than or equal to the current asteroid, then the current asteroid will be destroyed, and the algorithm can continue to the next asteroid in the list. If the top asteroid in the stack is smaller than the current asteroid, then the top asteroid will be destroyed, and the algorithm must continue to check whether the new top asteroid is smaller than the current asteroid, or whether the stack is empty.

The time complexity of this algorithm is O(n), where n is the number of asteroids in the list, since we only iterate through the list once. The space complexity is also O(n), since we store all the un-destroyed asteroids in the stack.

1