🌌 Understanding the “Asteroid Collision” Algorithm 🌠

Let’s look into one interesting coding interview question which tests our knowledge of fundamentals of data structures and algorithms.

🌍 Problem Statement:

Imagine you’re in space observing asteroids. Some of these asteroids are moving to the right, and some are moving to the left. What happens when they collide?

Given an array asteroids that represents the direction and magnitude of moving asteroids, your task is to find the state of the asteroids after all possible collisions.

🌟 Rules of Collision:

1. If two asteroids meet and they are moving in the same direction, they won’t collide.
2. If two asteroids meet and they are moving in opposite directions, the smaller asteroid explodes. If they are the same size, both explode.

💡 Intuition:

To solve this problem, we’ll use a stack. The stack will help us keep track of asteroids that are moving right and have not yet collided with any asteroids moving left. Whenever we encounter an asteroid moving left, we check the top of the stack to see if a collision occurs.

📜 Code Walkthrough:

Let’s examine the solution, step by step.

public int[] asteroidCollision(int[] asteroids) {
    Stack<Integer> stack = new Stack<>();
    for (int asteroid : asteroids) {
        if (asteroid > 0) {
            // Asteroid is moving to the right, push to stack
            stack.push(asteroid);
        } else {
            // Asteroid is moving to the left, check for collision
            while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -asteroid) {
                stack.pop(); // Asteroid moving right gets exploded
            }
            
            if (stack.isEmpty() || stack.peek() < 0) {
                stack.push(asteroid);
            } else if (stack.peek() == -asteroid) {
                stack.pop(); // Both asteroids explode
            }
        }
    }
    
    int[] result = new int[stack.size()];
    for (int i = result.length - 1; i >= 0; i--) {
        result[i] = stack.pop();
    }
    
    return result;
}

📚 Explanation

1. We initiate a stack to keep track of the asteroids.
2. As we iterate through the asteroids:
   a. If the asteroid is moving to the right (positive value), we simply push it to the stack.
   b. If it’s moving to the left (negative value), we check for potential collisions.
3. Inside the else block, we look for a collision:
   a. We loop while the top of the stack contains an asteroid moving to the right that’s smaller than our current asteroid. For each such asteroid, we pop it off the stack because it gets exploded.
   b. If the stack becomes empty or the top of the stack has an asteroid moving left, we push the current asteroid onto the stack.
   c. If the top of the stack has an asteroid of the same size but moving in the opposite direction, we pop it off the stack since both asteroids explode.
4. Finally, we convert the stack to an array for our result.

🎨 Illustration:

Imagine asteroids = [5, 10, -5].

1. Asteroid 5 is moving to the right, so we push it onto the stack.
2. Asteroid 10 is also moving to the right, so we push it too.
3. Asteroid -5 is moving to the left. The top of the stack is 10, which is moving in the opposite direction and is larger. Hence, -5 gets exploded, and our stack remains [5, 10].

⏲ Time Complexity:

We are iterating through the asteroids array once. For each asteroid, we either push it onto the stack or handle collisions by popping from the stack. Each asteroid is pushed or popped at most once, resulting in a linear number of operations. Therefore, the time complexity is O(n).

💾 Space Complexity:

In the worst case, we might push all the asteroids onto the stack. Thus, the space complexity is O(n).

If you enjoyed this explanation and found it enlightening, 🌟 please follow my blog. More to come!

Further Learning at DSAGuide.com
For an in-depth exploration of data structures, algorithms, and coding interview solutions, I invite you to visit DSAGuide.com. Elevate your understanding with our detailed guides on essential data structures, algorithms and coding interview problem solving.