MediumNeetCode150ArrayStackSimulation
Asteroid Collision
Simulate asteroid collisions.
Examples
Input
asteroids = [10,2,-5]
Output
[10]
2 and -5 collide.
Constraints
- •
2 <= asteroids.length <= 10^4 - •
-1000 <= asteroids[i] <= 1000 - •
asteroids[i] != 0
Approaches
Simulate step by step.
CodeT: O(n^2) | S: O(n) stack
Push positive, pop on collision.
CodeT: O(n) | S: O(n) stack
Same approach.
CodeT: O(n) | S: O(n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Simulation | O(n^2) | O(n) stack | Simulate step by step. |
| Stack | O(n) | O(n) stack | Push positive, pop on collision. |
| Stack Optimized | O(n) | O(n) | Same approach. |
Simulation
T: O(n^2)S: O(n) stack
Simulate step by step.
Stack
T: O(n)S: O(n) stack
Push positive, pop on collision.
Stack Optimized
T: O(n)S: O(n)
Same approach.
Common Mistakes
Wrong collision direction
Not handling all collisions
Off-by-one