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] != 0This 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.
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.
C++
Time Complexity: O(n) due to a single pass through the array.
Space Complexity: O(n) for potential stack usage in storing results.
| 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. |
L11. Aestroid Collisions | Stack and Queue Playlist • take U forward • 57,839 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