Funcia
Lv.1simulationstack

Asteroid Collision

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

asteroidsresult
[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

  • 1≤1 \le asteroids.length ≤200,000\le 200{,}000
  • −109≤-10^9 \le asteroids[i] ≤109\le 10^9, asteroids[i] ≠0\ne 0

Expected complexity

Time
O(N)
Space
O(N)

Examples

asteroidsExpected
[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 O(N)O(N). Rescanning for the next collision and erasing from the middle of the array is O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251368 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance603verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.