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.
This approach leverages a stack data structure to resolve collisions. We maintain a stack to keep track of the rightward-moving asteroids and resolve them when encountering leftward-moving asteroids. If the stack is empty or the asteroid is moving right, simply push it onto the stack. When encountering a leftward-moving asteroid, compare it to the stack's top. If the sizes are equal, both asteroids explode; if the stack's top is smaller, the stack's top asteroid explodes; otherwise, the current leftward-moving asteroid does not survive. Iterate through the entire list with these rules to achieve the desired result.
The function asteroidCollision initializes an empty list as a stack. It iterates over each asteroid and checks for a collision condition and resolves it by comparing the stack's top value with the current asteroid. Depending on the conditions, it either pops from the stack or appends to it while iterating through the entire list.
Python
JavaScript
Time Complexity: O(n). Each asteroid is pushed and popped from the stack at most once.
Space Complexity: O(n). In the worst case, all asteroids are moving in the same direction and are all stored in the stack.
This method involves using two pointers to manage the movement of asteroids in the array, with no additional stack usage. Although usually less intuitive than a stack approach, the two-pointer solution iteratively resolves collisions simultaneously moving both pointers forward and backward depending on conditions. However, a true two-pointer solution for asteroid collisions is typically not the ideal choice here compared to a stack-based method in terms of simplicity and efficiency.
This Java solution uses a Stack to properly manage asteroid collisions through a similar logic to the Python sample. The stack checks for ongoing collisions and resolves them according to magnitude. The final result is converted back to an array to meet function return requirements.
Time Complexity: O(n) due to a single pass through the array.
Space Complexity: O(n) for potential stack usage in storing results.
We traverse each asteroid x from left to right. Since each asteroid may collide with multiple asteroids before it, we consider using a stack to store.
x>0, it will definitely not collide with the previous asteroid, and we can directly push x into the stack.0, and the top element of the stack is less than -x, then the top element of the stack corresponds to the asteroid will explode, we loop to the top element of the stack Pop out until the condition is not satisfied. At this time, if the top element of the stack is equal to -x, then the two asteroids will explode, and we only need to pop the top element of the stack; if the stack is empty, or the top element of the stack is less than 0, then the current asteroid will not collide, we will push x into the stack.Finally, we return the elements in the stack as the answer.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array asteroids.
| Approach | Complexity |
|---|---|
| Stack-Based Approach | Time Complexity: O(n). Each asteroid is pushed and popped from the stack at most once. |
| Two Pointer Technique | Time Complexity: O(n) due to a single pass through the array. |
| Stack | — |
| 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. |
Asteroid Collision - Stack - Leetcode 735 • NeetCode • 71,363 views views
Watch 9 more video solutions →Practice Asteroid Collision with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor