Asteroid Collision

Problem Statement

In this problem, we are given an array asteroids, where each element contains an integer. These integers represent asteroids arranged in a sequence where each index corresponds to their relative position in space. The magnitude of each integer denotes the size of the asteroid, while its sign indicates the direction of its movement; positive values indicate movement to the right, and negative values to the left. All asteroids progress at the same uniform speed.

The primary goal is to deduce the final formation of these asteroids once all collisions have been resolved. Collision behavior is defined as follows: when two asteroids collide, the one with the smaller size is destroyed; if they are of equal size, both are destroyed. Asteroids moving in the same direction do not collide, facilitating a need to focus solely on opposing-direction interactions.

Examples

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

Approach and Intuition

To tackle this problem, the main challenge is to simulate the interactions correctly, considering directional movement and collision outcomes. Let's breakdown how the behavior of such a simulation may unfold using the examples:

1. Handling Directional Movement:

   • If an asteroid moves right and no other asteroid is encountered moving left, it continues its course unhindered.
   • Conversely, an asteroid moving left continues unless it encounters an asteroid moving right.

2. Collision Scenarios:

   • Two asteroids moving towards one another will always collide. The result of this collision depends on their sizes:
     • If one is larger, the smaller asteroid is destroyed.
     • If both are of equal size, both are destroyed.

Let’s expand this using provided examples:

• Example 1: asteroids = [5, 10, -5]
  • Asteroid 10 (moving right) encounters asteroid -5 (moving left). Since 10 is larger, -5 is destroyed, resulting in asteroids [5,10].
• Example 2: asteroids = [8, -8]
  • Here, both asteroids have equal size but opposite directions. Thus, both asteroids are destroyed, resulting in an empty array [].
• Example 3: asteroids = [10, 2, -5]
  • Asteroid 2 (moving right) encounters -5 (moving left). Given -5 is larger, asteroid 2 gets destroyed. Then, 10 and -5 (now remaining) collide, and since 10 is larger, -5 is destroyed. We are left with [10].

Logical Implementation:

• A typical solution can utilize a stack data structure:
  • Traverse the list of asteroids.
  • Use the stack to keep track and manage surviving asteroids.
  • For each asteroid, check if a collision occurs (i.e., a right-moving asteroid on the stack and a current left-moving asteroid).
  • Resolve collisions per the rules and update the stack accordingly.

The last step includes extracting the status of the stack once all elements are processed, which represents the state of asteroids post all collisions.

Solutions

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asts) {
        stack<int> asteroidsStack;
    
        for (int ast : asts) {
            bool pushToStack = true;
            while (!asteroidsStack.empty() && asteroidsStack.top() > 0 && ast < 0) {
                if (abs(asteroidsStack.top()) < abs(ast)) {
                    asteroidsStack.pop();
                    continue;
                } else if (abs(asteroidsStack.top()) == abs(ast)) {
                    asteroidsStack.pop();
                }
    
                pushToStack = false;
                break;
            }
                
            if (pushToStack) {
                asteroidsStack.push(ast);
            }
        }
    
        vector<int> resultAsteroids(asteroidsStack.size());
        for (int i = resultAsteroids.size() - 1; i >= 0; i--) {
            resultAsteroids[i] = asteroidsStack.top();
            asteroidsStack.pop();
        }
            
        return resultAsteroids;
    }
};