Problem of The Day: Asteroid Collision

Problem Statement

leetcode problem link

My Solution [Accepted]

public class Solution {
    public int[] AsteroidCollision(int[] asteroids) {
        Stack<int> stack = new Stack<int>();
        foreach(var asteroid in asteroids) {
            if (stack.Count == 0) {
                stack.Push(asteroid);
                continue;
            }
            else {
                if ((asteroid > 0 && stack.Peek() > 0) || (asteroid < 0 && stack.Peek() < 0))
                {
                    stack.Push(asteroid);
                    continue;
                }
                if (asteroid > 0)
                {
                    stack.Push(asteroid);
                }
                else if (asteroid < 0) {
                    while (stack.Count > 0 && stack.Peek() > 0 && Math.Abs(asteroid) > Math.Abs(stack.Peek())) {
                        stack.Pop();
                    }
                    if (stack.Count > 0 && stack.Peek() > 0 && Math.Abs(asteroid) == Math.Abs(stack.Peek())) {
                        stack.Pop();
                        continue;
                    }
                    if (stack.Count > 0 && stack.Peek() > 0)
                        continue;
                    stack.Push(asteroid);
                }
            }

        }

        return stack.Reverse().ToArray();
    }
}

Improve code

public class Solution {
    public int[] AsteroidCollision(int[] asteroids) {
        var stack = new Stack<int>();

        foreach (var asteroid in asteroids) {
            bool destroyed = false;

            // Only collision case: right-moving vs left-moving
            while (stack.Count > 0 && stack.Peek() > 0 && asteroid < 0) {
                int top = stack.Peek();

                if (Math.Abs(top) < Math.Abs(asteroid)) {
                    stack.Pop();          // top explodes
                    continue;
                }
                else if (Math.Abs(top) == Math.Abs(asteroid)) {
                    stack.Pop();          // both explode
                }

                destroyed = true;
                break;
            }

            if (!destroyed) {
                stack.Push(asteroid);
            }
        }

        return stack.Reverse().ToArray();
    }
}

Editorial

Approach: Stack

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        stack<int> st;

        for (int asteroid : asteroids) {
            int flag = 1;
            while (!st.empty() && (st.top() > 0 && asteroid < 0)) {
                // If the top asteroid in the stack is smaller, then it will explode.
                // Hence pop it from the stack, also continue with the next asteroid in the stack.
                if (abs(st.top()) < abs(asteroid)) {
                    st.pop();
                    continue;
                }
                // If both asteroids are the same size, then both asteroids will explode.
                // Pop the asteroid from the stack; also, we won't push the current asteroid to the stack.
                else if (abs(st.top()) == abs(asteroid)) {
                    st.pop();
                }

                // If we reach here, the current asteroid will be destroyed
                // Hence, we should not add it to the stack
                flag = 0;
                break;
            }

            if (flag) {
                st.push(asteroid);
            }
        }

        // Add the asteroids from the stack to the vector in the reverse order.
        vector<int> remainingAsteroids (st.size());
        for (int i = remainingAsteroids.size() - 1; i >= 0; i--){
            remainingAsteroids[i] = st.top();
            st.pop();
        }

        return remainingAsteroids;
    }
};