Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Stack & Queue

Asteroid Collision

Medium · Stack & Queue · Asked at Amazon, Google, Uber, Salesforce

Each asteroid moves along a line: positive = moving right, negative = moving left; the absolute value is its size. When a right-mover meets a left-mover, the smaller one explodes; if they are the same size, both explode. Asteroids moving in the same direction never meet. Print the asteroids left after all collisions (in order), or EMPTY if none survive.

Input

First line: n. Second line: n space-separated integers.

Output

The surviving asteroids, or EMPTY.

Constraints

Stack of survivors. A negative asteroid keeps colliding with positive asteroids on top of the stack until it explodes or the top is not positive.

Example 1

Input

3
5 10 -5

Output

5 10

Example 2

Input

2
8 -8

Output

EMPTY

Hints

  1. Only a right-mover (positive) followed later by a left-mover (negative) can collide.
  2. Keep the survivors on a stack. A negative asteroid fights the positive asteroids on top of the stack one by one.

Approach

Process asteroids left to right. A positive one is pushed. A negative one x collides while the top is positive: if the top is smaller than |x|, the top explodes (pop) and x keeps going; if equal, both explode; if larger, x explodes. If x survives (stack empty or top negative), push it. The stack, bottom to top, is the final state.

Complexity: O(n) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> st;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        bool alive = true;
        while (alive && x < 0 && !st.empty() && st.back() > 0) {
            if (st.back() < -x) st.pop_back();
            else {
                if (st.back() == -x) st.pop_back();
                alive = false;
            }
        }
        if (alive) st.push_back(x);
    }
    if (st.empty()) cout << "EMPTY\n";
    for (size_t i = 0; i < st.size(); i++) cout << st[i] << (i + 1 < st.size() ? " " : "\n");
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
st = []
for x in data[1:]:
    alive = True
    while alive and x < 0 and st and st[-1] > 0:
        if st[-1] < -x:
            st.pop()
        else:
            if st[-1] == -x:
                st.pop()
            alive = False
    if alive:
        st.append(x)
print(*st if st else ["EMPTY"])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] st = new int[n];
        int top = 0;
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            boolean alive = true;
            while (alive && x < 0 && top > 0 && st[top - 1] > 0) {
                if (st[top - 1] < -x) top--;
                else {
                    if (st[top - 1] == -x) top--;
                    alive = false;
                }
            }
            if (alive) st[top++] = x;
        }
        if (top == 0) {
            System.out.println("EMPTY");
            return;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < top; i++) sb.append(st[i]).append(i + 1 < top ? " " : "");
        System.out.println(sb);
    }
}

Solve Asteroid Collision online · All practice problems