Asteroid Collision

Med

#0689Time: O(N^2), where N is the number of asteroids. In the worst-case scenario, we might only resolve one collision per pass (e.g., a large left-moving asteroid at the end colliding with multiple smaller right-moving asteroids one by one). Since removing an element from an `ArrayList` can take O(N) time, and we might do this O(N) times, the complexity is quadratic.Space: O(N), where N is the number of asteroids. This is because we create a new `List` to hold the asteroids, which can store up to N elements.20 companies

Data structures

Array Stack

Companies

Accolite Deutsche Bank DoorDash EPAM Systems

Prompt

We are given an array asteroids of integers representing asteroids in a row. The indices of the asteriod in the array represent their relative position in space.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

Example 3:

Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Constraints:

2 <= asteroids.length <= 10⁴
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the collision process in a brute-force manner. It repeatedly scans the list of asteroids, finds the first pair that will collide, resolves the collision, and then restarts the scan. This continues until a full pass over the asteroids results in no collisions, at which point the asteroids are in a stable state.

Algorithm

1. Convert the input array asteroids to a List to allow for dynamic resizing and element removal.
1. Use a while loop that continues to run as long as collisions were found and resolved in the previous pass. A boolean flag can track this.
1. Inside the while loop, reset the flag and start a for loop to iterate through the current list of asteroids.
1. In the for loop, look for the first adjacent pair of asteroids (list[i], list[i+1]) that will collide. A collision occurs if list[i] is positive (moving right) and list[i+1] is negative (moving left).
1. If a colliding pair is found:
- a. Compare their absolute values to determine the outcome.
- b. If |list[i]| > |list[i+1]|, remove list[i+1].
- c. If |list[i]| < |list[i+1]|, remove list[i].
- d. If |list[i]| == |list[i+1]|, remove both asteroids.
- e. Set the boolean flag to true to indicate a collision happened, and break the inner for loop to restart the scan from the beginning of the modified list.
1. If the for loop completes without finding any collisions, the flag remains false, and the outer while loop terminates.
1. Convert the final stable list back to an array and return it.

Walkthrough

In this method, we use a dynamic data structure like an ArrayList in Java to store the asteroids, as it allows for easy removal of elements. We then enter a loop that continues as long as we are finding and resolving collisions. In each iteration of this main loop, we scan through the list to find the first instance of a right-moving asteroid followed immediately by a left-moving one.

When we find such a pair, we resolve the collision based on their sizes. The smaller asteroid (in absolute value) is removed. If they are of equal size, both are removed. After a collision is resolved, we must restart the scan from the beginning of the now-modified list, because the result of the collision could potentially cause a new collision with a preceding asteroid. The process terminates when we can complete a full scan of the list without any collisions occurring.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int[] asteroidCollision(int[] asteroids) {6        List<Integer> list = new ArrayList<>();7        for (int ast : asteroids) {8            list.add(ast);9        }10 11        boolean collisionOccurred = true;12        while (collisionOccurred) {13            collisionOccurred = false;14            for (int i = 0; i < list.size() - 1; i++) {15                // Check for a right-moving asteroid followed by a left-moving one16                if (list.get(i) > 0 && list.get(i+1) < 0) {17                    collisionOccurred = true; // A collision is found18                    if (Math.abs(list.get(i)) > Math.abs(list.get(i+1))) {19                        list.remove(i + 1);20                    } else if (Math.abs(list.get(i)) < Math.abs(list.get(i+1))) {21                        list.remove(i);22                    } else {23                        list.remove(i + 1);24                        list.remove(i);25                    }26                    // After a collision, restart the scan from the beginning27                    break;28                }29            }30        }31 32        // Convert the final list to an array33        int[] result = new int[list.size()];34        for (int i = 0; i < list.size(); i++) {35            result[i] = list.get(i);36        }37        return result;38    }39}

Complexity

Time

O(N^2), where N is the number of asteroids. In the worst-case scenario, we might only resolve one collision per pass (e.g., a large left-moving asteroid at the end colliding with multiple smaller right-moving asteroids one by one). Since removing an element from an `ArrayList` can take O(N) time, and we might do this O(N) times, the complexity is quadratic.

Space

O(N), where N is the number of asteroids. This is because we create a new `List` to hold the asteroids, which can store up to N elements.

Trade-offs

Pros

The logic is straightforward and directly models the problem description.
It's relatively easy to implement and understand for beginners.

Cons

Highly inefficient with a quadratic time complexity, O(N^2), which will be too slow for large inputs.
Repeatedly scanning the list from the beginning after each collision is computationally expensive.
Modifying a list while iterating over it adds complexity and potential for bugs if not handled carefully.

A much more efficient approach utilizes a Stack data structure. The logic is that collisions only happen when a right-moving asteroid is followed by a left-moving one. This 'last-in, first-out' interaction is perfectly modeled by a stack. We iterate through the asteroids, using the stack to keep track of the stable asteroids. An incoming asteroid only interacts with the one at the top of the stack.

Algorithm

1. Initialize an empty Stack to store the asteroids that have survived so far.
1. Iterate through each asteroid from the input array one by one.
1. For each asteroid:
- a. If the asteroid is positive (moving right), it won't collide with anything currently on the stack (as they are either also moving right or moving away). Push it onto the stack.
- b. If the asteroid is negative (moving left), it may collide with positive asteroids at the top of the stack. Use a while loop to handle these collisions:
  - The loop continues as long as the stack is not empty, the top element is positive, and the incoming asteroid is larger in magnitude (stack.peek() < -asteroid). In this case, the asteroid on the stack is destroyed, so pop it.
- c. After the while loop, check the state:
  - If the stack is now empty or the top element is also negative, the incoming asteroid survived without being destroyed. Push it onto the stack.
  - If the top element of the stack is positive and has the same size (stack.peek() == -asteroid), both are destroyed. pop the element from the stack and do not push the current asteroid.
  - If the top element is positive and larger (stack.peek() > -asteroid), the incoming asteroid is destroyed. Do nothing.
1. Once all asteroids have been processed, the stack contains the final state. Create a new array of the stack's size and populate it with the elements from the stack. Note that elements will be popped in reverse order.

Walkthrough

This optimal solution processes the asteroids in a single pass, achieving linear time complexity. We use a stack to maintain the collection of asteroids that are currently moving without collision.

We iterate through the input asteroids array. When we encounter a right-moving (positive) asteroid, it can't cause a collision with what's already in the stack, so we simply push it.

When we encounter a left-moving (negative) asteroid, a potential collision arises. We check the top of the stack. If the stack is empty or the top asteroid is also moving left, there's no collision, and we push the new asteroid. However, if the top is a right-moving (positive) asteroid, we handle the collision:

If the right-moving asteroid on the stack is smaller than the incoming left-moving one (in absolute value), the one on the stack is destroyed. We pop it and repeat the check with the new top of the stack.
If they are of equal size, both are destroyed. We pop the stack and discard the incoming asteroid.
If the right-moving asteroid on the stack is larger, the incoming left-moving one is destroyed. We do nothing further with it.

After iterating through all asteroids, the stack holds the final configuration. We then convert the stack's contents into an array to return.

1import java.util.Stack;2 3class Solution {4    public int[] asteroidCollision(int[] asteroids) {5        Stack<Integer> stack = new Stack<>();6        for (int ast : asteroids) {7            if (ast > 0) {8                // Right-moving asteroid, no immediate collision with stack contents9                stack.push(ast);10            } else { // ast < 0, left-moving asteroid11                // Destroy smaller right-moving asteroids on the stack12                while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -ast) {13                    stack.pop();14                }15                16                if (stack.isEmpty() || stack.peek() < 0) {17                    // If stack is empty or top is also left-moving, no collision18                    stack.push(ast);19                } else if (stack.peek() == -ast) {20                    // If same size, both are destroyed21                    stack.pop();22                } 23                // else stack.peek() > -ast, so incoming asteroid is destroyed. Do nothing.24            }25        }26 27        // Convert stack to array28        int[] result = new int[stack.size()];29        for (int i = result.length - 1; i >= 0; i--) {30            result[i] = stack.pop();31        }32        return result;33    }34}

Complexity

Time

O(N), where N is the number of asteroids. Each asteroid is pushed onto the stack at most once. While the inner `while` loop may run multiple times for a single incoming asteroid, each `pop` operation removes an element permanently. Thus, the total number of push and pop operations across the entire execution is proportional to N.

Space

O(N), where N is the number of asteroids. In the worst-case scenario, if all asteroids are moving in the same direction (e.g., all positive or all negative), they will all be pushed onto the stack.

Trade-offs

Pros

Optimal time complexity of O(N) as it processes each asteroid in a single pass.
The use of a stack provides an elegant and intuitive solution to the problem's collision dynamics.
Handles all collision cases efficiently and correctly.

Cons

Requires extra space for the stack, which can be O(N) in the worst case (e.g., all asteroids moving in the same direction).

Solutions

Solution

1class Solution {2public3  int[] asteroidCollision(int[] asteroids) {4    Deque<Integer> stk = new ArrayDeque<>();5    for (int x : asteroids) {6      if (x > 0) {7        stk.offerLast(x);8      } else {9        while (!stk.isEmpty() && stk.peekLast() > 0 && stk.peekLast() < -x) {10          stk.pollLast();11        }12        if (!stk.isEmpty() && stk.peekLast() == -x) {13          stk.pollLast();14        } else if (stk.isEmpty() || stk.peekLast() < 0) {15          stk.offerLast(x);16        }17      }18    }19    return stk.stream().mapToInt(Integer : : valueOf).toArray();20  }21}

1class Solution:2    def asteroidCollision(self, asteroids: List[int]) -> List[int]: stk = [] for x in asteroids: if x > 0: stk . append(x) else: while stk and stk[- 1] > 0 and stk[- 1] < - x: stk . pop() if stk and stk[- 1] == - x: stk . pop() elif not stk or stk[- 1] < 0: stk . append(x) return stk

1class Solution {2public:3  vector<int> asteroidCollision(vector<int> &asteroids) {4    vector<int> stk;5    for (int x : asteroids) {6      if (x > 0) {7        stk.push_back(x);8      } else {9        while (stk.size() && stk.back() > 0 && stk.back() < -x) {10          stk.pop_back();11        }12        if (stk.size() && stk.back() == -x) {13          stk.pop_back();14        } else if (stk.empty() || stk.back() < 0) {15          stk.push_back(x);16        }17      }18    }19    return stk;20  }21};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem