The Asteroid Collision Problem is a popular coding challenge often encountered in technical interviews and competitive programming contests. In this article, we will explore an efficient solution to this problem using a stack in C++.

Problem Statement

You are given an array asteroids, where each asteroid’s size and direction are represented as integers:

• Positive Integer: The asteroid is moving to the right.
• Negative Integer: The asteroid is moving to the left.

When two asteroids collide, the smaller one is destroyed. If both are of the same size, both are destroyed. The goal is to return the state of the asteroids after all collisions.

Example 1

Input: asteroids = [5, 10, -5]
Output: [5, 10]
Explanation: The asteroid -5 collides with 10 and is destroyed.

Example 2

Input: asteroids = [8, -8]
Output: []
Explanation: Both asteroids are of the same size and are destroyed.

Efficient Solution Using Stack

To simulate the asteroid collisions efficiently, we can use a stack. The main idea is to keep track of the right-moving asteroids and resolve collisions when a left-moving asteroid appears.

Approach

1. Use a Stack:
   • Push all right-moving asteroids into the stack.
2. Handle Collisions:
   • When a left-moving asteroid is encountered, compare it with the asteroid at the top of the stack.
   • Continue popping from the stack if the top asteroid is smaller.
3. Collision Rules:
   • If both asteroids are of equal size, both are destroyed.
   • If the left-moving asteroid is smaller, it gets destroyed.
   • If the stack is empty or the top asteroid is also left-moving, push the asteroid into the stack.

C++ Solution

Here is a clean and efficient solution in C++:

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        stack<int> st;
        for (int a : asteroids) {
            if (a > 0) {
                st.push(a);
            } else {
                while (!st.empty() && st.top() > 0 && st.top() < abs(a)) {
                    st.pop();
                }
                if (st.empty() || st.top() < 0) {
                    st.push(a);
                } else if (st.top() == abs(a)) {
                    st.pop();
                }
            }
        }
        vector<int> res(st.size());
        int i = st.size() - 1;
        while (!st.empty()) {
            res[i--] = st.top();
            st.pop();
        }
        return res;
    }
};

This C++ code defines a solution to the Asteroid Collision problem using a stack. Let’s break it down step-by-step.

Code Explanation:

1. Initialization

stack<int> st;

• A stack is used to simulate the collisions.
• It stores asteroids that are currently moving to the right (positive values).

2. Iterating through Asteroids

for(int a : asteroids) {

• Loop through each asteroid a in the array.

3. Handling Positive Asteroids

if(a > 0) {
    st.push(a);
}

• If the asteroid is moving to the right (a > 0), push it to the stack since it won’t collide immediately.

4. Handling Negative Asteroids (Potential Collision)

else {
    while(!st.empty() && st.top() > 0 && st.top() < abs(a)) {
        st.pop();
    }

• If the asteroid is moving to the left (a < 0), check for possible collisions.
• The asteroid at the top of the stack is moving to the right (st.top() > 0).
• Collision Condition:
  • If the current asteroid (a) has a greater size than the top of the stack (abs(a) > st.top()), it destroys the top asteroid. The top asteroid is removed using st.pop().
  • Continue this process until no further collisions are possible.

5. After the While Loop

if(st.empty() || st.top() < 0) {
    st.push(a);
}

• If the stack becomes empty (no right-moving asteroid left) or the top asteroid is also moving to the left (st.top() < 0), push the current asteroid a to the stack.

if(!st.empty() && st.top() == abs(a)){
    st.pop();
}

• If the top asteroid has the same size as the current asteroid, both are destroyed, and st.pop() is called.

6. Preparing the Result

vector<int> res(st.size());
int i = st.size() - 1;
while(!st.empty()) {
    res[i--] = st.top();
    st.pop();
}

• After processing all asteroids, the stack contains the remaining asteroids in the correct order.
• A result vector res is created with the size of the stack.
• The values are transferred from the stack to the result vector in reverse order using a while loop.

Final Return

return res;

• The result vector is returned as the final state of the asteroids.

✅ Time and Space Complexity

• Time Complexity: O(n)O(n) — Each asteroid is pushed and popped from the stack at most once.
• Space Complexity: O(n)O(n) — The stack stores the asteroids in the worst case.

This solution is efficient and elegant for simulating asteroid collisions using the stack-based approach.

Conclusion

The Asteroid Collision Problem in C++ can be solved effectively using a stack. This approach ensures clean and efficient management of asteroid collisions. Mastering this technique can help you tackle similar problems in coding interviews.

If you’d like to explore more algorithmic challenges or detailed C++ tutorials, stay tuned on PixelPen.tech! Happy coding!