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] != 0The key idea in Asteroid Collision is to simulate how asteroids interact as they move along a line. Each asteroid has a direction and size, and collisions only occur when a right-moving asteroid meets a left-moving one. A very effective way to model this interaction is by using a stack.
As you iterate through the array, push asteroids moving to the right onto the stack. When a left-moving asteroid appears, it may collide with the top elements of the stack. Compare sizes and resolve collisions by removing the smaller asteroid, repeating the process until the collision conditions are resolved. This structure naturally preserves the order of surviving asteroids while handling chain reactions of collisions.
This simulation-based strategy ensures each asteroid is processed at most once, leading to an efficient solution with O(n) time complexity and O(n) auxiliary space in the worst case.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack-based Simulation | O(n) | O(n) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Say a row of asteroids is stable. What happens when a new asteroid is added on the right?
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.
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.
1def asteroidCollision(asteroids):
2 stack = []
3 for ast in asteroids:
4 while stack and ast < 0 < stack[-1]:
5 if stack[-1] < -ast:
6 stack.pop()
7 continue
8 elif stack[-1] == -ast:
9 stack.pop()
10 break
11 else:
12 stack.append(ast)
13 return stackThe 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.
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.
Time Complexity: O(n) due to a single pass through the array.
Space Complexity: O(n) for potential stack usage in storing results.
1public int[] asteroidCollision(int[]Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Asteroid Collision is a common medium-level interview question and is often used to test understanding of stacks and simulation logic. Variations of this problem appear in coding interviews at major tech companies.
A stack is the most suitable data structure because it naturally models the last asteroid that could collide with the incoming one. It helps efficiently resolve chain collisions while maintaining the correct order of surviving asteroids.
The optimal approach uses a stack to simulate asteroid movements and collisions. As you iterate through the array, right-moving asteroids are pushed onto the stack, while left-moving ones resolve collisions with stack elements until stability is reached.
The problem involves resolving interactions with the most recent potential collider, which follows a Last-In-First-Out pattern. A stack allows you to repeatedly compare and remove asteroids during collisions in an efficient way.
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.