Asteroid Collision

Problem 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.

Examples

Constraints

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

Resolving Right and Left Collisions

A collision can only occur if an asteroid moving right (positive) is to the left of an asteroid moving left (negative). We can simulate this using a stack. We iterate through the asteroids.

• If the current asteroid is moving right (positive), we push it onto the stack since it cannot collide with anything currently to its left.
• If it is moving left (negative), it will collide with any right-moving asteroids at the top of the stack. While the stack has positive elements that are smaller than the absolute value of the current negative asteroid, those top elements explode (we pop them).
• If the top element is equal in size, both explode (we pop the top element and discard the current asteroid).
• If the top element is larger, the current asteroid explodes (we discard it).
• If the stack contains no positive elements at the top, the current negative asteroid is safe, and we push it onto the stack.

Solution 1: Collision Resolution Stack

Push safe asteroids onto a stack and resolve opposing direction meetings dynamically.

import java.util.Stack;

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();

        for (int ast : asteroids) {
            boolean alive = true;
            while (alive && ast < 0 && !stack.isEmpty() && stack.peek() > 0) {
                int diff = stack.peek() + ast;
                if (diff < 0) {
                    stack.pop(); // top asteroid explodes, continue collision check
                } else if (diff == 0) {
                    stack.pop(); // both explode
                    alive = false;
                } else {
                    alive = false; // current asteroid explodes
                }
            }
            if (alive) {
                stack.push(ast);
            }
        }

        int[] result = new int[stack.size()];
        for (int i = stack.size() - 1; i >= 0; i--) {
            result[i] = stack.pop();
        }
        return result;
    }
}

class Solution:
    def asteroidCollision(self, asteroids: list[int]) -> list[int]:
        stack = []
        for ast in asteroids:
            alive = True
            while alive and ast < 0 and stack and stack[-1] > 0:
                diff = stack[-1] + ast
                if diff < 0:
                    stack.pop()  # top asteroid explodes
                elif diff == 0:
                    stack.pop()  # both explode
                    alive = False
                else:
                    alive = False  # current asteroid explodes
                    
            if alive:
                stack.append(ast)
        return stack

#include <vector>
#include <cmath>

class Solution {
public:
    std::vector<int> asteroidCollision(std::vector<int>& asteroids) {
        std::vector<int> stack;

        for (int ast : asteroids) {
            bool alive = true;
            while (alive && ast < 0 && !stack.empty() && stack.back() > 0) {
                int diff = stack.back() + ast;
                if (diff < 0) {
                    stack.pop_back(); // top asteroid explodes
                } else if (diff == 0) {
                    stack.pop_back(); // both explode
                    alive = false;
                } else {
                    alive = false; // current asteroid explodes
                }
            }
            if (alive) {
                stack.push_back(ast);
            }
        }
        return stack;
    }
};

Complexity Analysis

• Time Complexity: O(n) since each asteroid is pushed and popped from the stack at most once.
• Space Complexity: O(n) auxiliary space to store elements in the stack.

Where It Breaks

If the velocity of the asteroids varies (instead of all moving at the same speed), the order of collisions cannot be determined solely by their initial positions, and this stack simulation breaks.

Common Mistakes

• Incorrect check conditions: Resolving collisions for stack.peek() < 0 and ast > 0. If the stack top is moving left and the incoming asteroid is moving right, they are moving away from each other and will never collide.
• Loop termination: Forgetting to set alive = false when the current asteroid explodes, which leads to infinite loops.

Frequently Asked Questions

Why does [-2, -1, 1, 2] have no collisions? The first two are moving left, and the last two are moving right. Since they are moving in opposite directions away from the center, they never cross paths.

How does this handle duplicate sizes? If stack.peek() + ast == 0, it indicates they are of equal sizes. The top asteroid is popped, and the incoming asteroid is discarded by setting alive = false.

← All Problems