Question
You're given an array of integers representing asteroids moving along a line. Each number indicates the asteroid's size and direction:
- Positive → moving right
- Negative → moving left
When two asteroids collide, the smaller one explodes. If they're the same size, both explode.
Return the state of the asteroids after all collisions.
Example
Input: [-2, -2, 4, 2, -3, -3, -5]
Output: [-2, -2, -5]
Explanation:
-2and-2move left, so no collision → push both.4and2move right → push both.-3comes in (going left):- It collides with
2→2is smaller →2explodes. - Now
4vs-3→4is bigger →-3explodes.
- It collides with
- Next
-3: again collides with4(still there) →4survives,-3explodes. - Now
-5: collides with4→4explodes. Then with-2(opposite direction) → both move left, so-5continues. Stack:[-2, -2, -5]
My Notes
- Use a stack to simulate moving asteroids.
- When current asteroid is going left and top of stack is moving right → possible collision.
- Handle collision cases:
- If same size → both explode
- If stack top is smaller → pop stack and continue checking
- If stack top is bigger → current asteroid explodes (do not push)
- Finally, the stack contains remaining asteroids.
package main
import (
"fmt"
)
type Stack struct {
items []int
}
func (s *Stack) Push(item int) {
s.items = append(s.items, item)
}
func (s *Stack) Pop() int {
popped := s.items[len(s.items)-1]
s.items = s.items[:len(s.items)-1]
return popped
}
func (s *Stack) Top() int {
return s.items[len(s.items)-1]
}
func (s *Stack) Empty() bool {
return len(s.items) == 0
}
func asteroidCollision(asteroids []int) []int {
stack := Stack{}
for _, val := range asteroids {
for !stack.Empty() && stack.Top() > 0 && val < 0 {
if stack.Top() == -val {
stack.Pop()
val = 0
continue
} else if stack.Top() < -val {
stack.Pop()
} else if stack.Top() > -val {
val = 0
}
}
if val != 0 {
stack.Push(val)
}
}
return stack.items
}
func main() {
result := asteroidCollision([]int{-2, -2, 4, 2, -3, -3, -5})
fmt.Println(result)
}