Asteroid Collision

Medium · Stack & Monotonic Stack · about 15 minutes

Asked at Amazon, Salesforce, Bloomberg, Microsoft, Meta, Google, Uber, Workday, Intuit, Okta, SAP, Gusto.

You are given an array asteroids of non-zero integers in a row. The absolute value is the asteroid's size and the sign its direction (positive moves right, negative moves left); all move at the same speed. When two asteroids meet, the smaller one explodes; if they are the same size, both explode. Asteroids moving in the same direction never meet. Return the state after all collisions.