Asteroid Collision

NeetCode: Asteroid Collision · LeetCode: 735. Asteroid Collision · Difficulty: Medium

Given an array asteroids of non-zero integers in a row. The absolute value is the size and the sign is the 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 of the asteroids after all collisions.

Example

Text

Input:  [5, 10, -5]     Output: [5, 10]
Input:  [8, -8]         Output: []
Input:  [10, 2, -5]     Output: [10]
Input:  [-2, -1, 1, 2]  Output: [-2, -1, 1, 2]

Brute force: repeat passes until nothing collides

Two asteroids can only collide when a right-mover is immediately followed by a left-mover. Scan for the first such adjacent pair, resolve it (remove the smaller, or both if equal), and start scanning again. Stop when a full scan finds no pair. Each collision removes at least one asteroid, so there are at most n collisions, but each costs a scan and an ArrayList.remove, which shifts the later elements, so it is quadratic. The method copies the input into an ArrayList<Integer> first, because an int[] cannot shrink. On a List<Integer>, remove(i) with an int argument removes by index.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

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

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.asteroidCollision(new int[]{5, 10, -5})));
        System.out.println(Arrays.toString(s.asteroidCollision(new int[]{8, -8})));
        System.out.println(Arrays.toString(s.asteroidCollision(new int[]{10, 2, -5})));
        System.out.println(Arrays.toString(s.asteroidCollision(new int[]{-2, -1, 1, 2})));
        System.out.println(Arrays.toString(s.asteroidCollision(new int[]{})));
    }
}

Output

[5, 10]
[]
[10]
[-2, -1, 1, 2]
[]

Time: O(n^2). Space: O(n) for the working copy.

Optimal: stack of survivors

Process the asteroids left to right, keeping the survivors so far in a stack. The top of the stack is the only one a new asteroid can hit first:

If the new asteroid moves right, or the stack is empty, or the top moves left, they can never meet: push it.
Otherwise the new asteroid moves left and the top moves right, so they collide. Compare sizes: if the top is smaller, pop it and keep fighting the next top; if equal, pop it and the new one is destroyed too; if the top is larger, the new one is destroyed.

The stack is an ArrayDeque<Integer>: push and pop work on the front, and peek reads the front. Popping returns the newest survivor first, so the last step fills the result array from its last index down to index 0. Each asteroid is pushed once and popped at most once, so the loop is linear overall.

Java

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

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) {
                int top = stack.peek();
                if (top < -a) {
                    stack.pop();
                } else {
                    if (top == -a) {
                        stack.pop();
                    }
                    alive = false;
                }
            }
            if (alive) {
                stack.push(a);
            }
        }
        int[] result = new int[stack.size()];
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] = stack.pop();
        }
        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.asteroidCollision(new int[]{5, 10, -5})));
        System.out.println(Arrays.toString(s.asteroidCollision(new int[]{8, -8})));
        System.out.println(Arrays.toString(s.asteroidCollision(new int[]{10, 2, -5})));
        System.out.println(Arrays.toString(s.asteroidCollision(new int[]{-2, -1, 1, 2})));
        System.out.println(Arrays.toString(s.asteroidCollision(new int[]{})));
    }
}

Output

[5, 10]
[]
[10]
[-2, -1, 1, 2]
[]

Time: O(n). Space: O(n).