Asteroid Collision | DSA & Design with Lucifer

Let's go to space 🚀 , suppose a huge bunch of asteroid are about to hit our planet earth and you are senior astrophysicist sitting at ISRO , and your task is to give an algorithm that determines if n asteroids are going to hit , we need to determine which asteroids survive after all collisions , there are some rules to determine this , if two asteroids are in opposite direction and they collide the one with larger value will stay and if they are of equal values they will destroy each other and lastly if they are in same direction they will stay in the same direction.

For example :-

inputs = [4 , -3 , 2, -5] (-ve sign shows the left direction of asteroids)
when,
asteroid -5 and 2 collide 5 would be left , array becomes [4,-3 , -5]
asteroid -5 and -3 would never collide because they are same direction
asteroid 4 and -3 , 4 would be left , so the array becomes [4,-5]
asteroid 4 and -5 will collide and give final array as [-5]

Now , what data structure to use ? When a left-mover arrives, it can only collide with the most recent right-mover (the top of the stack). After destroying it, the next most recent right-mover is the new top.

Can you see the LIFO pattern ? Stack or Deque would be the perfect data structure to use to store asteroids values.

Key Observation

A collision can only happen when:

positive asteroid
followed by
negative asteroid

Example:

[5, -3]

Collision possible.

But:

[-5, 3]

Collision impossible because they are moving away from each other.

Lets code this

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> survivors = new Stack<>();
        for (int val : asteroids) {
            if(val > 0) survivors.push (val); //we push the +ve values
            else {
                while (survivors.size()>0 && survivors.peek() < -val && survivors.peek() > 0) { //when peek is less than val and postive , we remove val from stack
                    survivors.pop();
                }
                if (survivors.size() > 0 && survivors.peek() == -val) {
                    survivors.pop(); //when they are equal both destroy each other
                } 
                else if ( survivors.size() > 0 && survivors.peek() > -val) {
                    //bigger one will explode you

                }
                else {
                    survivors.push(val);
                }
            }
        }

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

Time & Space Complexity — Asteroid Collision

Time Complexity — O(n)

The code has a for loop with a while loop inside — which looks like O(n²) at first glance. But it's actually O(n).

java

for (int ast : asteroids) {          // runs n times
    while (alive && ast < 0
           && !stack.isEmpty()
           && stack.peek() > 0) {    // looks scary — nested loop!
        ...
        stack.pop();
    }
    if (alive) stack.push(ast);
}

Why not O(n²)? — The push/pop argument

The key insight is:

Every asteroid is pushed at most once and popped at most once.

Total pushes across entire loop ≤ n
Total pops  across entire loop ≤ n

So total operations = pushes + pops ≤ 2n = O(n)

Think of it this way — an asteroid can only be popped if it was pushed. Since at most n asteroids get pushed total, at most n pops can ever happen total — across ALL iterations of the while loop combined, not per iteration.

That's it and you provided the right algo to save our planet.