Back to DSA

Asteroid Collision

medium
Acceptance: 47%
StackArraySimulation

An array of integers represents a row of asteroids. The absolute value indicates size and the sign indicates direction: positive travels right, negative travels left. All asteroids move at identical speed. Simulate all collisions and return the final surviving asteroids. When two collide, the smaller one is destroyed; if they are the same size, both are destroyed. Asteroids headed the same way never collide.

Examples

Example 1:
Input:asteroids = [3,7,-4]
Output:[3,7]
Example 2:
Input:asteroids = [10,-10]
Output:[]

Hints

Related Problems

Min StackmediumValid ParentheseseasyEvaluate Reverse Polish NotationmediumDaily TemperaturesmediumNext Greater Element Ieasy
00:00
import java.util.*;

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int a : asteroids) {
            boolean alive = true;
            while (alive && a < 0 && !stack.isEmpty() && stack.peek() > 0) {
                if (stack.peek() < -a) { stack.pop(); }
                else if (stack.peek() == -a) { stack.pop(); alive = false; }
                else { alive = false; }
            }
            if (alive) stack.push(a);
        }
        int[] result = new int[stack.size()];
        for (int i = result.length - 1; i >= 0; i--) result[i] = stack.pop();
        return result;
    }
}
Time complexityO(n)
Space complexityO(n)