Asteroid Collison [Stack]

87.Asteroid Collision

Stack

Simulation

Problem Statement:

Given an array asteroids representing the size and direction of asteroids, return the state of the asteroids after collisions. Positive integers represent asteroids moving right, and negative integers represent asteroids moving left. An asteroid will destroy the other if they collide, and only the larger one survives. If both are the same size, they both are destroyed.

Algorithm:

1. Use a stack to track asteroids that are still active.
2. For each asteroid in the input:
• If the asteroid is moving right (asteroid > 0), push it onto the stack.
• If the asteroid is moving left (asteroid < 0):
• Destroy smaller asteroids moving right in the stack until:
• The stack is empty,
• The asteroid moving right is larger, or
• A same-sized asteroid is destroyed.
• If no collision occurs, push the current asteroid onto the stack.
3. After processing all asteroids, the stack will contain the final state.

Complexity:

Time: O(n), where n is the number of asteroids | Space: O(n)

Java Implementation:

import java.util.Stack;

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

        for (int asteroid : asteroids) {
            if (asteroid > 0) {
                stack.push(asteroid); // Asteroid moving right
            } else {
                // Destroy all smaller asteroids in the stack moving right
                while (!stack.isEmpty() && stack.peek() > 0 && -asteroid > stack.peek()) {
                    stack.pop();
                }
                // Destroy both if sizes are equal
                if (!stack.isEmpty() && -asteroid == stack.peek()) {
                    stack.pop();
                } 
                // Push the left-moving asteroid if no collision
                else if (stack.isEmpty() || stack.peek() < 0) {
                    stack.push(asteroid);
                }
            }
        }

        // Prepare the result array
        int[] res = new int[stack.size()];
        int i = res.length - 1;
        while (!stack.isEmpty()) {
            res[i--] = stack.pop();
        }
        return res;
    }
}

Python Implementation:

def asteroidCollision(asteroids):
    stack = []

    for asteroid in asteroids:
        if asteroid > 0:
            stack.append(asteroid)  # Asteroid moving right
        else:
            # Destroy smaller asteroids in the stack moving right
            while stack and stack[-1] > 0 and -asteroid > stack[-1]:
                stack.pop()
            # Destroy both if sizes are equal
            if stack and stack[-1] > 0 and -asteroid == stack[-1]:
                stack.pop()
            # Push the left-moving asteroid if no collision
            elif not stack or stack[-1] < 0:
                stack.append(asteroid)

    return stack

C++ Implementation:

#include 
#include 
using namespace std;

vector asteroidCollision(vector& asteroids) {
    stack stack;

    for (int asteroid : asteroids) {
        if (asteroid > 0) {
            stack.push(asteroid); // Asteroid moving right
        } else {
            // Destroy smaller asteroids in the stack moving right
            while (!stack.empty() && stack.top() > 0 && -asteroid > stack.top()) {
                stack.pop();
            }
            // Destroy both if sizes are equal
            if (!stack.empty() && stack.top() > 0 && -asteroid == stack.top()) {
                stack.pop();
            } 
            // Push the left-moving asteroid if no collision
            else if (stack.empty() || stack.top() < 0) {
                stack.push(asteroid);
            }
        }
    }

    // Prepare the result array
    vector res(stack.size());
    for (int i = res.size() - 1; i >= 0; --i) {
        res[i] = stack.top();
        stack.pop();
    }
    return res;
}