Skip to content

Problem

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.

Constraints:

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

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.

Solve

Just imagine it not left right, but up and down. We used a stack to handle asteroids simulation:

  • Every asteroid adding to the stack, we check for collision, which meaning checking the sign of asteroid on then stack top, vs newly added one.
    • added asteroid (+) with value>0:The asteroids (-) and (+) in the stack have nothing to do with newly added asteroid (+)
    • added asteroid (-) with value<0: collision happen, simulation the collapsing until either:
      • All asteroid going up (+) explode, the stack remain the added asteroid (-).
      • Or added asteroid (-) being stop.

This should do the same in C:

/**

 * Note: The returned array must be malloced, assume caller calls free().
 */
int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize){
    int* stack = (int*)malloc(asteroidsSize * sizeof(int));
    int size = 0;
    int asteroid;
    for (int i = 0; i < asteroidsSize; i++){
        asteroid = asteroids[i];
        if (size == 0) {
            stack[size] = asteroid;
            size ++;
        }
        else if (stack[size-1] < 0 || asteroid > 0) {
            stack[size] = asteroid;
            size ++;
        }
        else {
            stack[size] = asteroid;
            while (size > 0 && stack[size-1] > 0 && stack[size] < 0) {
                if (stack[size-1] < -stack[size])
                    stack[size-1] = stack[size];
                else if (stack[size-1] == -stack[size])
                    stack[size-1] = 0;
                size--;
            }
            if (stack[size] != 0) size++;
        }
    }
    *returnSize = size;
    return stack;
}

minimal C code:

int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize){
    int *stack = (int *) malloc (asteroidsSize * sizeof(int));
    int k = -1; // no elements
    for(int i = 0; i<asteroidsSize; i++){
        k++;
        stack[k] = asteroids[i];
        while(k > 0 && stack[k] < 0 && stack[k-1] > 0){
            if(abs(stack[k]) > abs(stack[k-1])){
                stack[k-1] = stack[k];
                k--;
            } else if(abs(stack[k]) == abs(stack[k-1])){
                k = k - 2;
            } else {
                k--;
            }
        }

    }
    *returnSize = k + 1;
    return stack;
}

While this, is python implementation

class Solution(object):
    def asteroidCollision(self, asteroids):
        stack = []

        for asteroid in asteroids:
            while stack and asteroid < 0 < stack[-1]:
                if stack[-1] < -asteroid:
                    stack.pop()
                elif stack[-1] == -asteroid:
                    stack.pop()
                    break
                else:
                    break
            else:
                stack.append(asteroid)

        return stack

Last update : October 13, 2023
Created : August 16, 2023