We are given an array asteroids of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.
Example 1:
Input: asteroids = [5,10,-5] Output: [5,10] Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
Example 2:
Input: asteroids = [8,-8] Output: [] Explanation: The 8 and -8 collide exploding each other.
Example 3:
Input: asteroids = [10,2,-5] Output: [10] Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
Example 4:
Input: asteroids = [-2,-1,1,2] Output: [-2,-1,1,2] Explanation: The -2 and -1 are moving left, while the 1 and 2 are moving right. Asteroids moving the same direction never meet, so no asteroids will meet each other.
Constraints:
2 <= asteroids.length <= 10^4-1000 <= asteroids[i] <= 1000asteroids[i] != 0
The description was taken from https://leetcode.com/problems/asteroid-collision/.
#O(N) Time, O(N) Space
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
stack = []
for asteroid in asteroids:
if stack and stack[-1] > 0 and asteroid < 0:
stack.append(asteroid)
while len(stack) > 1 and stack[-2] > 0 and stack[-1] < 0:
if abs(stack[-2]) > abs(stack[-1]):
stack.pop()
elif abs(stack[-2]) < abs(stack[-1]):
bigger = stack.pop()
stack.pop()
stack.append(bigger)
else:
stack.pop()
stack.pop()
else:
stack.append(asteroid)
return stackIf we were to traverse the list to find out whether an asteroid is going to collide with a previous one, we would first need to remember what the previous asteroid was.
Stacks are perfect for this because the last asteroid we put in will be the first one we'd take out.
We can solve this problem by traversing the list of asteroids and if we see a negative asteroid, an asteroid that is left bound, and the top of our stack is a positive asteroid, an asteroid that is right bound, we will enter a loop where we continuously collide each asteroid we can within the stack based on the given collision procedures.
Once we have finished, the output will be the remaining asteroids in the stack.
Let's start by initializing our stack.
stack = []
For each asteroid in the asteroids list, if we encounter a negative asteroid and the top of our stack is a positive asteroid, we will push the new asteroid into the stack to begin collisions.
for asteroid in asteroids:
if stack and stack[-1] > 0 and asteroid < 0:
stack.append(asteroid)
While the length of the stack is at least two asteroids, and the top two asteroids are going to collide, we will continue our collisions.
while len(stack) > 1 and stack[-2] > 0 and stack[-1] < 0:
If the right bound asteroid is greater than the left bound asteroid, then the left bound asteroid will explode so we will pop it off of our stack.
if abs(stack[-2]) > abs(stack[-1]):
stack.pop()
If the right bound asteroid is smaller than the left bound asteroid, then the right bound asteroid will explode.
If this is the case, we will pop the left bound one from our stack and save it to a temporary variable, pop the right bound off and then push back in the left bound one.
elif abs(stack[-2]) < abs(stack[-1]):
bigger = stack.pop()
stack.pop()
stack.append(bigger)
Otherwise, these two asteroids are the same size so they will both explode and be popped off.
else:
stack.pop()
stack.pop()
However, if the asteroid we encountered wasn't going to collide with the asteroid on the top of our stack, we will just push it onto the stack.
else:
stack.append(asteroid)
Once we have finished traversing the asteroids array, we will return the remaining asteroids in the stack.
return stack