Log inSign up
mediumLeetCodeNot Started

Asteroid Collision

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Stack
Solve on LeetCode
Lesson

Problem Statement

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 (+ meaning right, - meaning left). Each asteroid moves at the same constant 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 · Standard Right vs Left Collision:

Input: asteroids = [5, 10, -5]
Output: [5, 10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 move right and never collide.

Example 2 · Mutual Annihilation:

Input: asteroids = [8, -8]
Output: []
Explanation: The 8 and -8 collide and explode each other completely.

Example 3 · Cascading Collisions:

Input: asteroids = [10, 2, -5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. Then 10 and -5 collide resulting in 10.

Constraints:

  • 2 <= asteroids.length <= 104
  • -1000 <= asteroids[i] <= 1000
  • asteroids[i] != 0

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the invariant condition for collision: positive on stack meeting an incoming negative.
  • Understand why a stack provides O(N) amortized time since each asteroid is pushed and popped at most once.
  • Handle mutual annihilation and chain reaction explosions cleanly without extra array shifts.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Algorithmic Decision Tree:

  • If asteroid > 0, push directly to stack.
  • If asteroid < 0, while stack is non-empty and stack.top > 0 and stack.top < |asteroid|, pop stack (top explodes).
  • If stack.top == |asteroid|, pop stack and mark current as destroyed (both explode).
  • If stack.top > |asteroid|, current explodes without popping top.
  • If stack is empty or stack.top < 0, push negative asteroid to stack.

Connected Patterns:

Daily TemperaturesNext Greater ElementSimplify Path

1. Repeated Array Passes Simulation

Intuition

Repeatedly scan the array and simulate adjacent collisions (+ followed by -) until a full scan completes with zero collisions.

Algorithm

  1. Step 1: Convert the initial array into a dynamic list.
  2. Step 2: Start a loop with a boolean flag hasCollided = true.
  3. Step 3: Scan indices i from 0 to list.size() - 2. If list[i] > 0 and list[i+1] < 0, resolve the collision by removing the smaller or both, set hasCollided = true, and restart the pass.
  4. Step 4: Terminate when a complete pass finds no colliding pairs.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <cmath>
4
5class Solution {
6public:
7 std::vector<int> asteroidCollision(std::vector<int>& asteroids) {
8 std::vector<int> res = asteroids;
9 bool collided = true;
10 while (collided) {
11 collided = false;
12 std::vector<int> nextPass;
13 int n = res.size();
14 for (int i = 0; i < n; i++) {
15 if (i < n - 1 && res[i] > 0 && res[i + 1] < 0) {
16 collided = true;
17 if (res[i] > std::abs(res[i + 1])) {
18 nextPass.push_back(res[i]);
19 } else if (res[i] < std::abs(res[i + 1])) {
20 nextPass.push_back(res[i + 1]);
21 }
22 i++; // skip pair
23 } else {
24 nextPass.push_back(res[i]);
25 }
26 }
27 res = nextPass;
28 }
29 return res;
30 }
31};
32
33int main() {
34 Solution solver;
35 std::vector<int> asteroids = {5, 10, -5};
36 std::vector<int> result = solver.asteroidCollision(asteroids);
37 std::cout << "Result: [";
38 for (size_t i = 0; i < result.size(); i++) {
39 std::cout << result[i] << (i + 1 < result.size() ? ", " : "");
40 }
41 std::cout << "]" << std::endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(N^2) — In the worst case (e.g. [1, 2, 3, 4, -5]), each pass only resolves one collision and shifts the array, taking O(N) per pass across O(N) passes.
  • Space complexity: O(N) — Requires O(N) auxiliary space to construct subsequent array states during passes.

Why Brute Force Doesn't Scale:

A chain reaction like [1, 2, 3, 4, 5, -6] triggers 5 separate array passes.

With N = 10,000, O(N2) takes ~108 operations, risking TLE.

2. Vector Two-Pointer Simulation

Intuition

Instead of creating full copies each round, process elements sequentially into a dynamic array, popping colliding items from the back.

Algorithm

  1. Step 1: Create an array result to serve as a simulation buffer.
  2. Step 2: Iterate through each asteroid in asteroids.
  3. Step 3: If asteroid is positive, push to result.
  4. Step 4: If negative, check the back of result. While back > 0 and back < |asteroid|, remove the back.
  5. Step 5: Handle equal size destruction (pop back and mark current as destroyed) or keep current if back is also negative / empty.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <cmath>
4
5class Solution {
6public:
7 std::vector<int> asteroidCollision(std::vector<int>& asteroids) {
8 std::vector<int> buffer;
9 for (int a : asteroids) {
10 bool alive = true;
11 while (alive && a < 0 && !buffer.empty() && buffer.back() > 0) {
12 if (buffer.back() < -a) {
13 buffer.pop_back();
14 } else if (buffer.back() == -a) {
15 buffer.pop_back();
16 alive = false;
17 } else {
18 alive = false;
19 }
20 }
21 if (alive) {
22 buffer.push_back(a);
23 }
24 }
25 return buffer;
26 }
27};
28
29int main() {
30 Solution solver;
31 std::vector<int> asteroids = {10, 2, -5};
32 std::vector<int> res = solver.asteroidCollision(asteroids);
33 std::cout << "Result: [";
34 for (size_t i = 0; i < res.size(); i++) {
35 std::cout << res[i] << (i + 1 < res.size() ? ", " : "");
36 }
37 std::cout << "]" << std::endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N) — Using a single dynamically managed vector as an explicit buffer avoids full repeated array recreations.
  • Space complexity: O(N) — O(N) buffer storage for surviving asteroids.

3. Optimal Stack Simulation

Intuition

A stack perfectly models LIFO sequential collisions. When a negative asteroid arrives, it interacts in reverse order with preceding positive asteroids until resolved.

Algorithm

  1. Step 1: Initialize an empty stack of integers.
  2. Step 2: Iterate through each asteroid a in asteroids.
  3. Step 3: If a > 0, push a directly to stack.
  4. Step 4: If a < 0, while stack has positive asteroids with value < -a, pop them.
  5. Step 5: If stack top is positive and == -a, pop top and mark a destroyed. If stack top > -a, mark a destroyed. Otherwise (stack empty or top is negative), push a.
  6. Step 6: Convert stack to output array in correct order.

Asteroid Collision Simulation

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
5 moves right, pushed to stack
Visual state
Values and pointers at this exact step
stack
TOP
5
Push adds to the top · Pop removes from the top
Why this step matters

5 moves right, pushed to stack.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 std::vector<int> asteroidCollision(std::vector<int>& asteroids) {
7 std::vector<int> st;
8 for (int a : asteroids) {
9 bool alive = true;
10 while (alive && a < 0 && !st.empty() && st.back() > 0) {
11 if (st.back() < -a) {
12 st.pop_back(); // top explodes, a continues
13 } else if (st.back() == -a) {
14 st.pop_back(); // both explode
15 alive = false;
16 } else {
17 alive = false; // a explodes, top survives
18 }
19 }
20 if (alive) {
21 st.push_back(a);
22 }
23 }
24 return st;
25 }
26};
27
28int main() {
29 Solution solver;
30 std::vector<int> asteroids = {5, 10, -5};
31 std::vector<int> res = solver.asteroidCollision(asteroids);
32 std::cout << "Result: [";
33 for (size_t i = 0; i < res.size(); i++) {
34 std::cout << res[i] << (i + 1 < res.size() ? ", " : "");
35 }
36 std::cout << "]" << std::endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N) — Each asteroid is pushed onto the stack at most once and popped at most once, yielding strictly linear O(N) time.
  • Space complexity: O(N) — O(N) worst-case space when all asteroids survive without colliding (e.g. all positive or all negative).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Repeated Array PassesO(N^2)O(N)Simulate pair collisions pass by pass with array copying.Rebuilding array for each single collision event.
2.Vector Two-Pointer SimulationO(N)O(N)Maintain an explicit buffer vector and mutate back element.Memory reallocations.
3.Optimal Stack SimulationOptimalO(N)O(N)Push positive asteroids; resolve incoming negative against stack top.None (Theoretical optimum).

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Assuming all opposite sign pairs collide (forgetting that [-2, 2] never collide).

Pitfall 2:

Forgetting to handle equal size mutual annihilation, causing one asteroid to remain.

Pitfall 3:

Popping from an empty stack without checking bounds.

Crucial Edge Cases to Validate:

  • All moving right (all positive) — No collisions occur; entire array is preserved.
  • All moving left (all negative) — No collisions occur; entire array is preserved.
  • Left-moving followed by right-moving (e.g. `[-2, 2]`) — They move away from each other; no collision occurs.
  • Mutual annihilation (e.g. `[8, -8]`) — Both asteroids explode, resulting in an empty output [].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explicitly explain the physical direction model before coding: + moves right, - moves left.
  2. Emphasize that [-1, 1] results in [-1, 1] because they move away from each other.
  3. Use a boolean flag like alive to cleanly track whether the incoming asteroid survived after battling the stack top.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Under what condition does an asteroid collision take place?

2.What is the amortized time complexity of the stack-based approach?

Back to DSA Sheet