Drone Collisions Along a One-Dimensional Corridor

Implement simulateCollisions

A row of drones all launch along the same straight corridor at the same instant. Each entry in arr gives one drone's launch speed and direction: positive means flying right, negative means flying left, and the magnitude is its size. Whenever a right-flying drone and a later left-flying drone meet, they collide: the smaller one is destroyed, or both are destroyed if they're equal in size. Two drones flying the same direction — or flying apart from each other — never meet. Return the sizes and directions of the drones left standing, in their original left-to-right order. A single left-to-right pass with a stack of survivors handles every collision in one shot: a newly arriving drone only ever needs to fight the drone currently on top of the stack (the nearest survivor to its left), and if it wins, it keeps fighting whatever's now on top after that one's destroyed — a possible chain reaction — until it either loses, ties, or clears the stack entirely. Since each drone is pushed onto the stack once and can be popped off at most once for good, the whole simulation finishes in O(n), instead of the brute force's repeated O(n) rescans after every single collision.

Example 1:

Input: arr = [4,-9,6]

Output: [-9,6]

Example 2:

Input: arr = [15,3,-8]

Output: [15]

Example 3:

Input: arr = [-3,4,-5,6]

Output: [-3,-5,6]

+ 3 hidden test cases run on Submit.

Constraints:

  • 1 ≤ arr.length ≤ 12
  • -100 ≤ arr[i] ≤ 100, and arr[i] ≠ 0
  • A positive value means a drone flying right with that speed; a negative value means flying left, with size equal to |arr[i]|
  • All drones start moving at the same instant

arr =

[4, -9, 6]