# Asteroid Collision
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/asteroid-collision)
Canonical: https://scaleengineer.com/dsa/problems/asteroid-collision
**Data structures:** Array, Stack
**Companies:** [Accolite](https://scaleengineer.com/companies/accolite), [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [DoorDash](https://scaleengineer.com/companies/doordash), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Flipkart](https://scaleengineer.com/companies/flipkart), [Myntra](https://scaleengineer.com/companies/myntra), [ServiceNow](https://scaleengineer.com/companies/servicenow), [SoFi](https://scaleengineer.com/companies/sofi), [Zoho](https://scaleengineer.com/companies/zoho), [Lyft](https://scaleengineer.com/companies/lyft), [Salesforce](https://scaleengineer.com/companies/salesforce), [Zynga](https://scaleengineer.com/companies/zynga), [Citadel](https://scaleengineer.com/companies/citadel), [PhonePe](https://scaleengineer.com/companies/phonepe), [Sprinklr](https://scaleengineer.com/companies/sprinklr), [Dream11](https://scaleengineer.com/companies/dream11), [Roku](https://scaleengineer.com/companies/roku), [Qualtrics](https://scaleengineer.com/companies/qualtrics), [OpenAI](https://scaleengineer.com/companies/openai), [IMC](https://scaleengineer.com/companies/imc)
---
## Problem
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 <= 104`
* `-1000 <= asteroids[i] <= 1000`
* `asteroids[i] != 0`

# Approaches
## Brute-Force Simulation
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.
**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.
**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.
### Explanation
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.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        List<Integer> list = new ArrayList<>();
        for (int ast : asteroids) {
            list.add(ast);
        }

        boolean collisionOccurred = true;
        while (collisionOccurred) {
            collisionOccurred = false;
            for (int i = 0; i < list.size() - 1; i++) {
                // Check for a right-moving asteroid followed by a left-moving one
                if (list.get(i) > 0 && list.get(i+1) < 0) {
                    collisionOccurred = true; // A collision is found
                    if (Math.abs(list.get(i)) > Math.abs(list.get(i+1))) {
                        list.remove(i + 1);
                    } else if (Math.abs(list.get(i)) < Math.abs(list.get(i+1))) {
                        list.remove(i);
                    } else {
                        list.remove(i + 1);
                        list.remove(i);
                    }
                    // After a collision, restart the scan from the beginning
                    break;
                }
            }
        }

        // Convert the final list to an array
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}
```
### Algorithm
- 1. Convert the input array `asteroids` to a `List` to allow for dynamic resizing and element removal.
- 2. 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.
- 3. Inside the `while` loop, reset the flag and start a `for` loop to iterate through the current list of asteroids.
- 4. 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).
- 5. 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.
- 6. If the `for` loop completes without finding any collisions, the flag remains `false`, and the outer `while` loop terminates.
- 7. Convert the final stable list back to an array and return it.

## Efficient Stack-based Approach
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.
**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.
**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).
### Explanation
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:
1.  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.
2.  If they are of equal size, both are destroyed. We pop the stack and discard the incoming asteroid.
3.  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.

```java
import java.util.Stack;

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int ast : asteroids) {
            if (ast > 0) {
                // Right-moving asteroid, no immediate collision with stack contents
                stack.push(ast);
            } else { // ast < 0, left-moving asteroid
                // Destroy smaller right-moving asteroids on the stack
                while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -ast) {
                    stack.pop();
                }
                
                if (stack.isEmpty() || stack.peek() < 0) {
                    // If stack is empty or top is also left-moving, no collision
                    stack.push(ast);
                } else if (stack.peek() == -ast) {
                    // If same size, both are destroyed
                    stack.pop();
                } 
                // else stack.peek() > -ast, so incoming asteroid is destroyed. Do nothing.
            }
        }

        // Convert stack to array
        int[] result = new int[stack.size()];
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] = stack.pop();
        }
        return result;
    }
}
```
### Algorithm
- 1. Initialize an empty `Stack` to store the asteroids that have survived so far.
- 2. Iterate through each `asteroid` from the input array one by one.
- 3. 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.
- 4. 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.

# Solutions
### Java

```java
class Solution {
public
  int[] asteroidCollision(int[] asteroids) {
    Deque<Integer> stk = new ArrayDeque<>();
    for (int x : asteroids) {
      if (x > 0) {
        stk.offerLast(x);
      } else {
        while (!stk.isEmpty() && stk.peekLast() > 0 && stk.peekLast() < -x) {
          stk.pollLast();
        }
        if (!stk.isEmpty() && stk.peekLast() == -x) {
          stk.pollLast();
        } else if (stk.isEmpty() || stk.peekLast() < 0) {
          stk.offerLast(x);
        }
      }
    }
    return stk.stream().mapToInt(Integer : : valueOf).toArray();
  }
}

```

### Python

```python
class Solution:
    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

```

### CPP

```cpp
class Solution {
public:
  vector<int> asteroidCollision(vector<int> &asteroids) {
    vector<int> stk;
    for (int x : asteroids) {
      if (x > 0) {
        stk.push_back(x);
      } else {
        while (stk.size() && stk.back() > 0 && stk.back() < -x) {
          stk.pop_back();
        }
        if (stk.size() && stk.back() == -x) {
          stk.pop_back();
        } else if (stk.empty() || stk.back() < 0) {
          stk.push_back(x);
        }
      }
    }
    return stk;
  }
};

```