735. Asteroid Collision

📝 Problem Details

• Title: 735. Asteroid Collision
• Link: https://leetcode.com/problems/asteroid-collision/
• Difficulty: Medium
• Tags/Categories: Stack

input array asteroids representing asteroids in a row asteroids[i] represent their relative position in space abs(asteroid[i]) represents its size positive / negative value represents its direction (positive meaning right, negative meaning left) each asteroid moves at the same speed (two asteroids moving in the same directions will never meet since they are moving at the same speed) if two asteroids meet, the smaller one will explode if both are the same size, both will explode return the sate of the asteroids after all collisions

💭What Were My Initial Thoughts?

can use a stack to manage collisions

💡 Explanation of Solution

Stack based approach:
- iterate through asteroids while maintaining a stack to trakc active asteroids
- if the current asteroid is moving right (+) , push it to the stack
- if the current asteroid is moving left (-) , check for potential collisions
	- if the top of the stack is positive (+), compare sizes
		- the smaller asteroid explodes
		- if same size, both explode
		- if asteroid[i] survives, keep checking
	- if the stack is empty of the top is also (-), simply push the asteroid

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

💻 Implementation of Solution

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        stack<int> st;
 
        for (int asteroid : asteroids) {
            bool destroyed = false;
 
            while (!st.empty() && st.top() > 0 && asteroid < 0) { // Potential collision
                int top = st.top();
 
                if (abs(asteroid) > abs(top)) {
                    st.pop();  // Destroy top asteroid, continue checking
                } else if (abs(asteroid) == abs(top)) {
                    st.pop();  // Both explode
                    destroyed = true;
                    break;
                } else {
                    destroyed = true; // The new asteroid is destroyed
                    break;
                }
            }
 
            if (!destroyed) {
                st.push(asteroid);
            }
        }
 
        // Convert stack to vector (Reverse order)
        vector<int> result(st.size());
        for (int i = st.size() - 1; i >= 0; i--) {
            result[i] = st.top();
            st.pop();
        }
        return result;
    }
};