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
- 1 ≤ n ≤ 10^5
- 1 ≤ |a[i]| ≤ 1000
- a[i] ≠ 0
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
- Only a right-mover (positive) followed later by a left-mover (negative) can collide.
- 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);
}
}