Asteroid Collision

MEDIUM✓ CHIP-TIMEDLC #735 — FULL STATEMENT ↗

The drill: Simulate a row of asteroids drifting left or right — sign gives direction, magnitude gives size. Same-size collisions destroy both; unequal ones destroy the smaller. Return whatever survives, left to right.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A row of asteroids arrives as an array of nonzero integers. Each value's sign gives its direction — positive drifts right, negative drifts left — and its magnitude gives its size.

Two asteroids collide only when a right-moving one is immediately followed, later in the row, by a left-moving one closing the gap between them. On collision, the smaller one is destroyed; equal sizes destroy both.

Asteroids moving the same direction never catch each other and never collide. The drill hands back whatever asteroids remain once every possible collision has played out, left to right.

EX 01

asteroids = [5, 10, -5]

→ [5, 10]

SMALLER ASTEROID DESTROYED ON IMPACT

EX 02

asteroids = [8, -8]

→ []

EQUAL SIZES MUTUALLY DESTROY

EX 03

asteroids = [10, 2, -5]

→ [10]

LARGE SURVIVOR EATS A CHAIN OF SMALLER RIGHT-MOVERS

row holds up to a couple thousand asteroids
sizes range widely and are never zero
equal-size collisions destroy both asteroids
same-direction asteroids never collide with each other

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A collision only ever happens between a right-mover and the very next left-mover after it — same-direction asteroids never catch each other. What needs to be remembered as you scan?

HINT 2 THE STRUCTURE

A stack holds “survivors confirmed so far.” A new left-mover only has to fight the top of the stack if that top is moving right; keep resolving until it can't fight (or the stack empties), then push whatever's left of it.

HINT 3 ONE STEP FROM THE ANSWER

For each value: while the top is a smaller right-mover than an incoming left-mover, pop it (destroyed). If the top's magnitude equals the incomer's, pop it and the incomer too. Otherwise, if the top is a larger or equal right-mover, the incomer is destroyed and nothing pushes.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE SURVIVORS STACKPATTERN · STACK OF SURVIVORSasteroids = [5, 10, -6, -10, -20]

-6

-10

-20

SURVIVOR STACK

— empty —

STEP 1

Right-movers push freely; a left-mover fights the top of the stack while that top is a smaller or equal right-mover.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/asteroid-collision.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []
        for a in asteroids:
            alive = True
            while alive and a < 0 and stack and stack[-1] > 0:
                if stack[-1] < -a:
                    stack.pop()
                    continue
                elif stack[-1] == -a:
                    stack.pop()
                alive = False
            if alive:
                stack.append(a)
        return stack

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 15 LN

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        a = asteroids[:]
        changed = True
        while changed:
            changed = False
            for i in range(len(a) - 1):
                if a[i] > 0 and a[i + 1] < 0:
                    if a[i] == -a[i + 1]:
                        del a[i:i + 2]
                    elif a[i] < -a[i + 1]:
                        del a[i]
                    else:
                        del a[i + 1]
                    changed = True
                    break
        return a

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 17 LN

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int a : asteroids) {
            boolean alive = true;
            while (alive && a < 0 && !stack.isEmpty() && stack.peek() > 0) {
                if (stack.peek() < -a) {
                    stack.pop();
                    continue;
                } else if (stack.peek() == -a) {
                    stack.pop();
                }
                alive = false;
            }
            if (alive) {
                stack.push(a);
            }
        }
        int[] result = new int[stack.size()];
        int i = result.length - 1;
        for (int v : stack) {
            result[i--] = v;
        }
        return result;
    }
}

TIME O(N)SPACE O(N)JAVA · RACE PACE · 26 LN

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

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 33 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED