735. Asteroid Collision Medium

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.

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

Example 2:
Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

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

Approach

Input: An integer array asteroids, each element representing an asteroid's direction and size (positive right, negative left).

Output: Return an array of the surviving asteroids after all collisions have concluded.

This problem is a typical Stack + Pair Elimination Simulation problem.

We use a stack stack to simulate the planets still in flight:

• Traverse through each asteroid in the array;
• If the current asteroid is heading right (positive), or the stack is empty, or the top asteroid is also heading left (negative) -> No collision, push it directly onto the stack;
• If the current asteroid is heading left (negative), and the top asteroid is heading right (positive), a collision occurs:
  • If the absolute value of the current asteroid is greater, the top asteroid is destroyed, and the current asteroid continues to compare with the new top of the stack;
  • If both sizes are equal, they both explode, and the current asteroid is not pushed.
  • If the top asteroid is greater, the current asteroid is destroyed, and we terminate the comparison.
• After traversal, the remaining elements in the stack are the asteroids that have not been destroyed.

Implementation

python

from typing import List

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []  # Stack to hold the asteroids still in motion

        for asteroid in asteroids:
            # Mark whether the current asteroid is destroyed
            alive = True

            # If current asteroid flies left (negative) and the top flies right (positive), collision may occur
            while stack and asteroid < 0 < stack[-1]:
                if abs(asteroid) > stack[-1]:
                    # Current asteroid is bigger, top one explodes, continue comparing next top
                    stack.pop()
                elif abs(asteroid) == stack[-1]:
                    # Both are the same, they both explode
                    stack.pop()
                    alive = False
                    break
                else:
                    # Top one is bigger, current asteroid explodes
                    alive = False
                    break

            # If the current asteroid is still alive, push it
            if alive:
                stack.append(asteroid)

        return stack

javascript

/**
 * @param {number[]} asteroids
 * @return {number[]}
 */
const asteroidCollision = function(asteroids) {
    const stack = [];

    for (let speed of asteroids) {
        let alive = true;

        while (stack.length && stack.at(-1) > 0 && speed < 0) {
            if (stack.at(-1) > Math.abs(speed)) {
                alive = false;
                break;
            } else if (stack.at(-1) < Math.abs(speed)) {
                stack.pop();
            } else {
                alive = false;
                stack.pop();
                break
            }
        }

        if (alive) stack.push(speed);
    }

    return stack;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Links

735. Asteroid Collision (English)

735. 小行星碰撞 (Chinese)