LeetCode 735: Asteroid Collision Solution

Master LeetCode problem 735 (Asteroid Collision), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

735. Asteroid Collision

Medium

Array Stack Simulation

Problem Explanation

Explanation:

We can use a stack to simulate the asteroid collisions. We iterate through the array of asteroids, and for each asteroid:

If it's a positive asteroid or the stack is empty or the top of the stack is negative, we push it onto the stack.
If it's a negative asteroid and the top of the stack is positive, we compare their sizes to determine if they collide. If the negative asteroid has a larger absolute size, we pop the positive asteroid from the stack. If they are equal sizes or the positive asteroid is larger, we skip the negative asteroid.
If the negative asteroid causes all positive asteroids on top of the stack to explode, we continue popping until the stack is empty or a negative asteroid is on top. Solution:

Solution Code

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        
        for (int asteroid : asteroids) {
            if (asteroid > 0 || stack.isEmpty() || stack.peek() < 0) {
                stack.push(asteroid);
            } else {
                while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < Math.abs(asteroid)) {
                    stack.pop();
                }
                if (!stack.isEmpty() && stack.peek() == Math.abs(asteroid)) {
                    stack.pop();
                } else if (stack.isEmpty() || stack.peek() < 0) {
                    stack.push(asteroid);
                }
            }
        }
        
        int[] result = new int[stack.size()];
        for (int i = stack.size() - 1; i >= 0; i--) {
            result[i] = stack.pop();
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 735 (Asteroid Collision)?

This page provides optimized solutions for LeetCode problem 735 (Asteroid Collision) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 735 (Asteroid Collision)?

The time complexity for LeetCode 735 (Asteroid Collision) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 735 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 735 in Java, C++, or Python.

Back to LeetCode Solutions