Stack· 25 min

Asteroid Collision

LeetCode #735 · Medium · Interactive step-by-step visualization

Setup

Example inputasteroids = [5,10,-5]
Step 1 / 8

Current step

1 / 8

Incoming asteroid 5. A collision happens only when a right-moving stack top meets a left-moving asteroid. No opposing pair at the top, so nothing collides.

Step log

asteroids (positive moves right, negative moves left)

Read
5
0
10
1
-5
2
Collision stack · top on right
Active cursor
Comparing
Best or completed
Leaving or removed
asteroid-collision.java
1public int[] asteroidCollision(int[] asteroids) {
2    Deque<Integer> stack = new ArrayDeque<>();
3    for (int asteroid : asteroids) {
4        boolean alive = true;
5        while (alive && asteroid < 0 && !stack.isEmpty() && stack.peekLast() > 0) {
6            int top = stack.peekLast();
7            if (top < -asteroid) stack.removeLast();
8            else { if (top == -asteroid) stack.removeLast(); alive = false; }
9        }
10        if (alive) stack.addLast(asteroid);
11    }
12    return stack.stream().mapToInt(Integer::intValue).toArray();
13}
● Java
Time
O(n)
Space
O(n)
Pattern
stack
Frames
8
25 / 75