We are given an array asteroids of integers representing asteroids in a row. The indices of the asteriod in the array represent their relative position in space.
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.
Constraints:
2 <= asteroids.length <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0
Implementations
Python
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
stack = []
for asteroid in asteroids:
if asteroid > 0:
stack.append(asteroid)
else:
# Incoming asteroid is bigger, remove many as needed
while stack and stack[-1] > 0 and stack[-1] < abs(asteroid):
stack.pop()
# Both explode
if stack and stack[-1] > 0 and stack[-1] == abs(asteroid):
stack.pop()
# Add initial and as many negatives
elif not stack or stack[-1] < 0:
stack.append(asteroid)
return stack
🐍The Stack: Our Asteroid Holding Area
Think of stack as a place where we temporarily keep the asteroids we've seen so far, in the order we encountered them. It helps us keep track of who's going to collide with whom.
🐍Going Through Each Asteroid
The code looks at each asteroid in the asteroids list, one by one.
🐍Positive Asteroids (Moving Right)
If an asteroid is positive (moving right), it’s safe for now. We simply add it to the stack. It will only collide with something coming from the right, which we haven't seen yet.
🐍Negative Asteroids (Moving Left) — The Collisions
- If an asteroid is negative (moving left), things get interesting. It’s going to start colliding with positive asteroids in the stack.
🐍“While Loop: Bigger Negative Eats Smaller Positives”
- The while loop checks if there are positive asteroids in the stack that are smaller than the absolute value (size) of the current negative asteroid.
- If there are, it means the negative asteroid is bigger and destroys them, so we remove those positive asteroids from the stack using stack.pop().
🐍Equal Size: Boom!
- After the while loop, we check if the top of the stack is a positive asteroid that is the same size as the negative asteroid. If so, they both explode, and we remove the positive one with stack.pop().
🐍Negative Survives or Nothing to Collide With
If the stack is empty (meaning no positive asteroids were left), or if the top of the stack is a negative asteroid, it means the current negative asteroid survives. We add it to the stack.
🐍The Survivors
- After processing all the asteroids, the stack contains the asteroids that survived all the collisions, in the order they should be.
Typescript
function asteroidCollision(asteroids: number[]): number[] {
const stack: number[] = [];
for (const asteroid of asteroids) {
if (asteroid > 0) {
stack.push(asteroid);
} else {
while (stack.length > 0 && stack[stack.length - 1] > 0 && stack[stack.length - 1] < Math.abs(asteroid)) {
stack.pop();
}
if (stack.length > 0 && stack[stack.length - 1] > 0 && stack[stack.length - 1] === Math.abs(asteroid)) {
stack.pop();
} else if (stack.length === 0 || stack[stack.length - 1] < 0) {
stack.push(asteroid);
}
}
}
return stack;
}
🟡The Stack (Imagine a Line of Asteroids):
- We use a “stack,” which is like a line where we can only add or remove asteroids from the end. This stack will hold the asteroids that survive.
🟡Looking at Each Asteroid One by One:
- The function goes through each asteroid in the given list.
- Right-Moving Asteroids (Positive Numbers):
- If an asteroid is moving to the right (positive), it won’t collide with anything in our stack yet, so we just add it to the end of the stack.
🟡Left-Moving Asteroids (Negative Numbers):
- If an asteroid is moving to the left (negative), it might collide with asteroids in the stack.
🟡Checking for Collisions:
- We look at the last asteroid in the stack (the one at the end of our line).
- If the last asteroid is moving to the right (positive) and is smaller than the left-moving asteroid (negative), the right-moving asteroid explodes (we remove it from the stack).
- We keep removing right moving asteroids from the end of the stack, as long as they are smaller than the absolute value of the current negative asteroid.
🟡Same Size Collision:
- If the last asteroid in the stack is moving to the right (positive) and is the same size as the left-moving asteroid (ignoring the direction), they both explode (we remove the last asteroid from the stack).
🟡No Collision or Left-Moving Survives:
- If the stack is empty, or the last asteroid in the stack is moving to the left (negative), the left-moving asteroid survives, and we add it to the end of the stack.
🟡The Survivors:
- After checking all the asteroids, the ones left in the stack are the asteroids that survived the collisions. The function returns this stack.
Go
func asteroidCollision(asteroids []int) []int {
stack := []int{}
for _, asteroid := range asteroids {
if asteroid > 0 {
stack = append(stack, asteroid)
} else {
for len(stack) > 0 && stack[len(stack)-1] > 0 && stack[len(stack)-1] < -asteroid {
stack = stack[:len(stack)-1]
}
if len(stack) > 0 && stack[len(stack)-1] > 0 && stack[len(stack)-1] == -asteroid {
stack = stack[:len(stack)-1]
} else if len(stack) == 0 || stack[len(stack)-1] < 0 {
stack = append(stack, asteroid)
}
}
}
return stack
}
🔵Going Right? Stack It!
- If an asteroid is going right (positive number), we simply put it on top of our stack. It’s safe for now.
🔵Going Left? Collision Time!
- If an asteroid is going left (negative number), it’s going to hit anything on the stack that’s going right.
- Smaller Right Ones Explode: We keep checking the top of the stack. If it’s a right-moving asteroid (positive) and smaller than our left-moving one, it explodes (we remove it from the stack).
- Same Size? Both Explode: If the top of the stack is a right-moving asteroid with the same size as our left-moving one, they both explode (we remove it from the stack).
🔵Left Survives or Nothing to Collide:
- If the stack is now empty, or the top of the stack is a left-moving asteroid (negative), our left-moving asteroid survives, and we add it to the stack.
- if the left moving asteroid has been destroyed during the collision loop, it is never added to the stack.
🔵The Survivors:
- Finally, the stack contains the asteroids that survived all the collisions, in the order they’re still flying.
If you liked this content I’d appreciate an upvote or a comment. That helps me improve the quality of my posts as well as getting to know more about you, my dear reader.
Muchas gracias!
Follow me for more content like this.
X | PeakD | Rumble | YouTube | Linked In | GitHub | PayPal.me | Medium
Down below you can find other ways to tip my work.
BankTransfer: "710969000019398639", // CLABE
BAT: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
ETH: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
BTC: "33xxUWU5kjcPk1Kr9ucn9tQXd2DbQ1b9tE",
ADA: "addr1q9l3y73e82hhwfr49eu0fkjw34w9s406wnln7rk9m4ky5fag8akgnwf3y4r2uzqf00rw0pvsucql0pqkzag5n450facq8vwr5e",
DOT: "1rRDzfMLPi88RixTeVc2beA5h2Q3z1K1Uk3kqqyej7nWPNf",
DOGE: "DRph8GEwGccvBWCe4wEQsWsTvQvsEH4QKH",
DAI: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875"