Drone Collisions Along a One-Dimensional Corridor

Medium25–30 min

Topics

StackArraySimulation

Companies

AmazonGoogleBloomberg

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.

Test Case 1:

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

Output:[-9, 6]

Explanation:4 (flying right) meets -9 (flying left, bigger) and is destroyed; -9 survives and keeps flying left. 6 (flying right, launched after) never meets -9, since -9 is already ahead of it moving the opposite way.

Test Case 2:

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

Output:[15]

Explanation:-8 first meets 3 (smaller) and destroys it, then keeps going and meets 15 (bigger), which destroys -8 in turn. Only 15 survives.

Test Case 3:

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

Output:[-3, -5, 6]

Explanation:-3 flies left with nothing ahead of it, so it survives. 4 (right) meets -5 (left): equal in the sense that -5 is bigger (5>4), so 4 is destroyed and -5 survives. 6 (right) never meets anything moving toward it.

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

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Repeatedly Rescan for the Next Collision

Brute

Keep a working list of surviving drones. Repeatedly scan it from the beginning looking for the first adjacent pair still capable of colliding (a right-flier immediately followed by a left-flier). Resolve that one collision — removing the smaller drone, or both if they're equal in size — then restart the scan from the beginning, since removing drones can create brand-new adjacent pairs anywhere in the list. Keep going until a full scan finds no more colliding pairs. Correct, but each collision resolved can trigger a fresh O(n) scan, and there can be up to O(n) collisions, giving O(n²) overall.

TimeO(n²)

SpaceO(n)

Java

Try it out

class Solution {
    public int[] simulateCollisions(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int x : arr) list.add(x);
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i < list.size() - 1; i++) {
                if (list.get(i) > 0 && list.get(i + 1) < 0) {
                    int a = list.get(i), b = -list.get(i + 1);
                    if (a < b) {
                        list.remove(i);
                    } else if (a > b) {
                        list.remove(i + 1);
                    } else {
                        list.remove(i + 1);
                        list.remove(i);
                    }
                    changed = true;
                    break;
                }
            }
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) result[i] = list.get(i);
        return result;
    }
}

Optimal — Single-Pass Stack of Survivors

Optimal

Process drones left to right, keeping a stack of survivors seen so far. A new drone only ever collides with a right-flying drone currently on top of the stack, and only if the new drone itself flies left (any two drones moving the same direction, or moving apart, can never meet). Resolve that single collision immediately: if the stack's top is smaller, pop it and keep checking against what's now on top (a chain of destructions is possible); if they're equal, both are destroyed; if the stack's top is bigger, the new drone is destroyed and nothing changes below it. Once the new drone either survives or is destroyed, move to the next one. Each drone is pushed at most once and popped at most once, so total work is O(n).

TimeO(n)