Quick Overview

Resolve all collisions among asteroids moving left or right along one line, preserving survivors in original order. Use a stack to model only opposing-direction collisions and repeatedly compare any current asteroid that survives a smaller opponent.

Resolve Collisions Between Moving Asteroids

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement `remaining_asteroids(asteroids)`. Each nonzero integer represents an asteroid moving along one line. Its absolute value is its size; positive values move right and negative values move left. A collision can occur only when a right-moving asteroid is immediately to the left of a left-moving asteroid. The smaller asteroid is destroyed, and equal-sized asteroids destroy each other. Return the surviving asteroids in their original left-to-right order after all collisions finish. For example, `[5, 10, -5]` becomes `[5, 10]`, while `[-2, -1, 1, 2]` is unchanged. ```hint Only one direction pair can collide A stack is stable until its top moves right and the current asteroid moves left. ``` ```hint The current asteroid may survive several collisions After destroying a smaller stack top, compare the same current asteroid again. Push it only if it has not been destroyed. ```

Quick Answer: Resolve all collisions among asteroids moving left or right along one line, preserving survivors in original order. Use a stack to model only opposing-direction collisions and repeatedly compare any current asteroid that survives a smaller opponent.

Each nonzero integer is an asteroid whose sign gives direction and whose absolute value gives size. Resolve every collision between a right-moving asteroid on the left and a left-moving asteroid on the right, then return survivors in their original order.

Constraints

  • 0 <= asteroids.length <= 3,000.
  • Every asteroid is a nonzero integer whose absolute value is at most 10^12.
  • Equal-sized opposing asteroids destroy each other; same-direction asteroids never collide.

Examples

Input: ([],)

Expected Output: []

Explanation: No asteroids produce no survivors.

Input: ([5, 10, -5],)

Expected Output: [5, 10]

Explanation: The larger right-moving asteroid survives the final collision.

Hints

  1. Only a right-moving survivor followed by a new left-moving asteroid can create unresolved work.
  2. A left-moving asteroid may outlive several smaller opponents, so keep comparing it until it dies or becomes stable.

Loading coding console...