735. Asteroid Collision - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
You are given an integer array asteroids where each element represents an asteroid:

The absolute value represents the size.
The sign represents the direction: positive for rightward, negative for leftward.

When two asteroids collide:

The smaller one (by absolute value) explodes.
If both are of the same size, both explode.
Asteroids moving in the same direction never collide.

Return an array representing the state of the asteroids after all collisions.

Example 1:

Input: asteroids = [5, 10, -5]
Output: [5, 10]
Explanation:
The asteroid 10 and -5 collide. Since 10 is larger than 5, the -5 explodes. Asteroid 5 never collides with 10.

Example 2:

Input: asteroids = [8, -8]
Output: []
Explanation:
The asteroid 8 and -8 collide and both explode because they are of equal size.

Example 3:

Input: asteroids = [10, 2, -5]
Output: [10]
Explanation:
Asteroid 2 and -5 collide resulting in -5 surviving (since 5 > 2) but then 10 and -5 collide and 10 survives.

Hints

Hint 1:
Think about how asteroids moving to the right might eventually encounter asteroids moving to the left. Collisions occur only when a right-moving asteroid is followed by a left-moving one.
Hint 2:
A stack is a natural data structure for this problem because you can "simulate" the collisions as you iterate through the array, comparing the current asteroid with the ones that have not yet collided (stored on the stack).
Hint 3:
When the current asteroid is moving left (a negative value), repeatedly check the top of the stack (which represents a previous right-moving asteroid) to resolve collisions. Continue this process until either the current asteroid is destroyed, no collision is possible, or you’ve resolved all collisions with right-moving asteroids.

Approach: Using a Stack to Simulate Collisions

Idea

Initialize an Empty Stack:
Use a stack to keep track of asteroids that have not yet exploded. The stack will store asteroids in the order they appear after surviving collisions.
Iterate Through the Asteroids:
- If the current asteroid is moving right (positive), push it onto the stack because it may later collide with an asteroid moving left.
- If the current asteroid is moving left (negative), check the top of the stack:
  - While there is a right-moving asteroid on the top of the stack (positive) and collisions are possible:
    - Compare the sizes (absolute values).
    - If the top asteroid is smaller (absolute value) than the current one, pop the top asteroid (it explodes) and continue checking.
    - If the top asteroid is equal in size, pop it and do not push the current asteroid (both explode).
    - If the top asteroid is larger, the current asteroid explodes (do not push it) and stop checking.
- If no collision occurs (or all right-moving asteroids have been popped), push the current asteroid onto the stack.
Return the Stack:
After processing all asteroids, the stack will contain the surviving asteroids in order.

Why This Works

The stack helps you "remember" the last right-moving asteroids that could collide with an incoming left-moving asteroid.
By checking collisions in a loop, you can simulate the chain reaction where one collision leads to the possibility of another.

Code Implementation

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
- In the worst case, each asteroid may cause multiple collisions, but every asteroid is pushed and popped at most once.
- Overall: O(n), where n is the number of asteroids.
Space Complexity:
- The space required is O(n) in the worst case if no collisions occur (all asteroids survive).

Step-by-Step Walkthrough and Visual Example

Consider the input: [10, 2, -5]

Start with an empty stack.
Process asteroid 10:
- 10 is positive, so push it onto the stack → stack: [10].
Process asteroid 2:
- 2 is positive, so push it onto the stack → stack: [10, 2].
Process asteroid -5:
- -5 is negative; check the top of the stack:
  - Top is 2 (a right-moving asteroid). Compare sizes: | -5 | = 5 is greater than |2| = 2, so pop 2.
  - Continue checking: now the top is 10. Compare: | -5 | = 5 is less than |10| = 10, so the current asteroid (-5) explodes.
- The stack remains [10].
Final Result:
- The surviving asteroids are [10].

Common Mistakes and Edge Cases

Common Mistakes

Incorrect Collision Check:
Ensure collisions are only checked when the current asteroid is moving left (negative) and the top of the stack is moving right (positive).
Not Handling Equal Sizes Properly:
When two asteroids have the same absolute value, both should explode. Make sure to break out of the collision loop in that case.
Forgetting to Maintain Order:
After processing all collisions, the remaining asteroids in the stack represent the final order.

Edge Cases

All Asteroids Moving in the Same Direction:
No collisions occur; simply return the original array.
No Asteroids:
If the input array is empty, return an empty array.
Consecutive Collisions:
When a single left-moving asteroid collides with multiple right-moving asteroids, ensure that all possible collisions are resolved correctly.

Variations

Asteroid Collision with Different Rules:
Variations might change how collisions are resolved (e.g., allowing explosions to trigger secondary collisions).

Basic Stack Problems:
Use problems that require simulation with stacks to strengthen your understanding of this data structure.
Expression Evaluation:
Problems that require processing elements with a stack (e.g., evaluating arithmetic expressions).