Asteroid Collisions (Stack Approach)

Let’s say we have this 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.

To begin, we can imagine an example:

The values represent the size of the asteroid, and the -/+ attribute represents the direction (negative values move left and positive values move right).

If we illustrate the series of collisions that take place, it would look something like this:

We begin with all of our asteroids before they collide.

Then, asteroid with value +10 collides with the smaller asteroid -5, and eliminates it.

Then, asteroid with value +10 collides with a larger asteroid -15 and is subsequently eliminated.

Lastly, the asteroids with value +5 and -15 collide, with -15 destroying the smaller asteroid. We are left with an answer of [-15].

Solution

First, let’s look at the code before explaining it.

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

    for(int i=0; i<asteroids.length; i++) {
        int asteroid = asteroids[i];
        if(!stack.isEmpty() && stack.peek() > 0 && asteroid < 0) {

            // Equal (Both asteroids get destroyed)
            if(Math.abs(asteroid) == Math.abs(stack.peek())) {
                stack.pop();
            }

            // Current asteroid is bigger than one at top of stack
            // Top asteroid in stack gets destroyed
            // Re-check current asteroid with next in stack
            else if(Math.abs(asteroid) > Math.abs(stack.peek())) {
                stack.pop();
                i--;
            }
        }
        else {
            // No collision, add asteroid to stack
            stack.push(asteroid);
        }
    }


    // Build a new array (backwards stack)
    int[] res = new int[stack.size()];
    for(int i=stack.size()-1; i>=0; i--) {
        res[i] = stack.pop();
    }

    return res;
}

Explanation

We first begin with [5, 10, -5, -15] in our array of asteroids.

We loop through the array and add items to a stack if they meet any of the following requirements

• The stack is empty
• The top item (asteroid) in the stack is moving left
• The asteroid is moving right

We can see immediately that the first two asteroids in the array will be placed on the stack. During the first iteration, the stack is empty, so we add [5] to the stack.

In the second iteration, the asteroid is moving right, so we add 10 to the stack. [5, 10]

The third iteration, when the asteroid is -5 does not meet these conditions. We have the current asteroid moving left and the last asteroid in the stack was moving right. We will have a collision!

Since the asteroids -5 & 10 are not equivalent and the current asteroid -5 is not larger than the last asteroid in the stack, we do nothing. We do not add -5 to the stack, since it will be destroyed.

Then, we move to the last asteroid in the array, which is -15. Once again, the current asteroid (-15) is moving left and the last asteroid (10) is moving right, so we enter into the first if conditional.

We see that the current asteroid (-15) is larger than the last asteroid in the stack (10) so the collision will wipe out the last asteroid in the stack. We pop 10 from the stack. We also need to be sure not to iterate i since we need to keep checking -15’s next collisions.

Similarly, we check -15 against 5 and the same thing occurs. 5 is eliminated from the stack. i does not increment.

At the final iteration, the stack is empty, so we add -15 to the stack.

We return the inverse of the stack.

Please take a look at the following animation, as well.

Animation

Performance Analysis:

Time Complexity:

• The loop iterates over each asteroid once (O(n)), where n is the number of asteroids.
• Inside the loop, the stack operations (push, pop, peek) have an average time complexity of O(1), as stacks are typically implemented as dynamic arrays or linked lists.
• The loop only revisits an index when the current asteroid is larger than the one at the top of the stack, in which case the index i is decremented. This avoids unnecessary operations in most cases.

Overall, the time complexity of your algorithm is O(n), where n is the number of asteroids.

Space Complexity:

• The stack is used to store asteroids that haven’t collided yet. In the worst case, all asteroids could end up in the stack if they don’t collide.
• Therefore, the space complexity of the algorithm is O(n) as well, where n is the number of asteroids.

LeetCode Result