Asteroid Collision - Leetcode Solution

Problem Statement:

We are given an array of integers that represent asteroids. Each asteroid in the array has a size, which can be either positive or negative. Positive asteroids travel in the same direction as the given array, and negative asteroids travel towards the opposite direction.

The problem is to simulate the motion of all the asteroids. If two asteroids collide, then the smaller asteroid will be destroyed. If two asteroids are of the same size, then both asteroids will be destroyed. The final state of the asteroids array is the state after all collisions have occurred.

Solution:

To solve this problem, we can use a stack data structure to keep track of the asteroids that are still in motion. We can iterate through the given asteroids array and check the direction of each asteroid. If the asteroid is moving towards the right, we can simply push it onto the stack. If the asteroid is moving towards the left, then we need to check if there are any asteroids in the stack that are moving towards the right.

If there are no asteroids in the stack that are moving towards the right, then the current asteroid will continue moving towards the left. We can simply push it onto the stack.

If there is an asteroid in the stack that is moving towards the right, then we need to compare the sizes of the two asteroids. If the size of the asteroid in the stack is greater than the current asteroid, then the current asteroid will be destroyed. We can simply skip the current asteroid and continue iterating through the rest of the array.

If the size of the asteroid in the stack is smaller than the current asteroid, then we need to remove the asteroid from the stack and compare it with the next asteroid in the stack. We repeat this process until all collisions have been resolved.

We can implement the above approach using a stack, and the time complexity of this algorithm is O(n), where n is the number of asteroids in the array.

Solution Code:

def asteroidCollision(asteroids: List[int]) -> List[int]: stack = [] for asteroid in asteroids: if asteroid > 0: stack.append(asteroid) else: while stack and stack[-1] > 0 and stack[-1] < abs(asteroid): stack.pop() if not stack or stack[-1] < 0: stack.append(asteroid) elif stack[-1] == abs(asteroid): stack.pop() return stack

Explanation:

In the above code, we have used a stack to keep track of the asteroids that are still in motion. We iterate through the given asteroids array and check the direction of each asteroid.

If the asteroid is moving towards the right, we simply push it onto the stack.

If the asteroid is moving towards the left, we check if there are any asteroids in the stack that are moving towards the right.

If there are no asteroids in the stack that are moving towards the right, then the current asteroid will continue moving towards the left. We can simply push it onto the stack.

If there is an asteroid in the stack that is moving towards the right, we compare the sizes of the two asteroids.

If the size of the asteroid in the stack is greater than the current asteroid, then the current asteroid will be destroyed. We simply skip the current asteroid and continue iterating through the rest of the array.

If the size of the asteroid in the stack is smaller than the current asteroid, we remove the asteroid from the stack and compare it with the next asteroid in the stack. We repeat this process until all collisions have been resolved.

Finally, we return the stack, which contains the final state of the asteroids array after all collisions have occurred.

1