Watch 10 video solutions for Asteroid Collision, a medium level problem involving Array, Stack, Simulation. This walkthrough by NeetCode has 71,363 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 1000asteroids[i] != 0Problem Overview: You are given an array where each value represents an asteroid's size and direction. Positive values move right, negative values move left. When two asteroids moving in opposite directions meet, the smaller one explodes. If both are equal, both disappear. The task is to simulate these collisions and return the asteroids that remain.
Approach 1: Stack-Based Simulation (O(n) time, O(n) space)
This approach models the collision process using a stack. Iterate through the array and push asteroids moving right onto the stack. When a left-moving asteroid appears, it may collide with right-moving asteroids stored on the stack. Repeatedly compare the top of the stack with the incoming asteroid and resolve collisions by removing the smaller one. Equal sizes remove both. Each asteroid enters and leaves the stack at most once, which keeps the time complexity linear. This pattern is common in stack problems where elements interact with the most recent unresolved item.
The key insight is that collisions only happen when the previous asteroid moves right and the current one moves left. All other combinations never meet, so they can be pushed safely. This approach directly simulates the physics of the problem and works well for interview settings because the logic is easy to reason about and efficient.
Approach 2: Two Pointer Technique (O(n) time, O(1) extra space)
This variation treats the input array itself as the structure that stores surviving asteroids. Use one pointer to iterate through the array and another pointer to represent the position where the next surviving asteroid should be written. When a collision scenario appears, repeatedly compare the current asteroid with the last stored asteroid and resolve outcomes in place. The pointer moves backward when an asteroid is destroyed and forward when a survivor is confirmed.
This approach avoids an explicit stack by reusing the array as a simulated stack. The logic still mirrors the same collision rules: only right-moving asteroids before a left-moving asteroid can collide. Because each asteroid is processed a constant number of times, the runtime remains O(n). It is essentially an in-place simulation built on top of an array.
Recommended for interviews: The stack-based solution is what most interviewers expect. It clearly demonstrates understanding of collision conditions and stack behavior while maintaining O(n) time complexity. The two pointer version is a space-optimized refinement that shows deeper understanding of how stacks can be simulated in arrays.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Simulation | O(n) | O(n) | General case. Easiest to implement and most commonly expected in interviews. |
| Two Pointer In-Place Simulation | O(n) | O(1) | When minimizing extra memory or demonstrating in-place stack simulation. |