Asteroid Collision

Explanation & Solution

Description

We are given an array asteroids of integers representing asteroids in a row.

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.

Input:asteroids = [5,10,-5]

-5

Output:[5,10]

Explanation: The 10 and -5 collide, 10 survives. The 5 and 10 never collide.

Constraints

2 <= asteroids.length <= 10^4
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0

Approach

Stacks pattern

1. Stack Simulation

Use a stack to track surviving asteroids from left to right

2. Collision Detection

A collision only happens when:
The current asteroid moves left (negative)
The top of the stack moves right (positive)
Same-direction or both-negative asteroids never collide

3. Resolve Collisions

While there's a collision scenario:
If the right-moving asteroid is smaller: pop it (destroyed), continue checking
If equal size: pop the right-moving one, mark current as destroyed too
If the right-moving asteroid is larger: current asteroid is destroyed, stop

4. Push Survivors

If the current asteroid wasn't destroyed, push it onto the stack

Key Insight

The stack maintains all surviving asteroids — collisions only happen at the boundary between right-moving and left-moving asteroids
A single left-moving asteroid can destroy multiple right-moving ones (chain reaction)
Time: O(n), Space: O(n)

Solution Code

Decode String

Next Greater Element I