Asteroid Collision
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Asteroids on a line are given from left to right in asteroids. The absolute value is an asteroid's size and the sign its
direction: positive moves right, negative moves left, all at the same speed. When a right-mover meets a left-mover, the
smaller one explodes; if they are the same size, both explode. Asteroids moving the same way never meet.
Return the asteroids left after all collisions, from left to right (an empty array if none remain).
Examples
| asteroids | result |
|---|---|
[5, 10, -5] | [5, 10] |
[8, -8] | [] |
[10, 2, -5] | [10] |
Example 3 — -5 destroys 2, then explodes against 10.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(asteroids: int[]) → int[]
Constraints
-
asteroids.length -
asteroids[i],asteroids[i]
Expected complexity
- Time
- O(N)
- Space
- O(N)
Examples
| asteroids | Expected |
|---|---|
[5,10,-5] | [5,10] |
[8,-8] | [] |
[10,2,-5] | [10] |
Hint
Hint
Scan from the left and keep the survivors on a stack. Push right-movers. For a left-mover, collide it with the stack top while the top moves right: pop smaller tops and continue, pop an equal top and stop, or let the incoming one explode against a bigger top. A surviving left-mover is pushed. Each asteroid is pushed and popped at most once, so this is . Rescanning for the next collision and erasing from the middle of the array is and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1368 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 3 | verdict only |