algoadvance

Leetcode 735. Asteroid Collision

Problem Statement

We are given an array asteroids of integers representing asteroids in a row.

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 not 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:

Clarifying Questions

  1. Are the sizes and directions of the asteroids guaranteed to be non-zero integers within the specified range?
  2. Can we assume that the array asteroids always contains at least two elements?
  3. Is there any specific way we need to handle the output format, or should it just be a vector of integers?

Strategy

To solve this problem, we’ll use a stack to simulate the collision process:

  1. Traverse each asteroid from left to right.
  2. For each asteroid:
    • If it’s moving to the right (>0), push it on the stack.
    • If it’s moving to the left (<0), handle collisions with the stack’s top asteroids iteratively:
      • Compare its absolute size with the top of the stack.
      • If the top of the stack is smaller, pop the stack, and continue to check the next top.
      • If the top of the stack is larger, the current asteroid explodes, no push occurs.
      • If both sizes are equal, both explode (pop the stack and do not push the current).
      • If the stack is empty or the top is a left-moving asteroid, push the current asteroid.
  3. The remaining asteroids in the stack are the final state after all collisions.

Code

#include <vector>
#include <stack>

std::vector<int> asteroidCollision(std::vector<int>& asteroids) {
    std::stack<int> st; // stack to keep track of asteroids
    
    for (int ast : asteroids) {
        bool exploded = false; // flag to check if the current asteroid exploded
        
        while (!st.empty() && ast < 0 && st.top() > 0) { 
            if (st.top() < -ast) { // top of stack asteroid explodes
                st.pop();
            } else if (st.top() == -ast) { // both asteroids explode
                st.pop();
                exploded = true;
                break;
            } else { // current asteroid explodes
                exploded = true;
                break;
            }
        }
        
        if (!exploded) {
            st.push(ast);
        }
    }
    
    // Convert stack to vector
    std::vector<int> result(st.size());
    for (int i = st.size() - 1; i >= 0; --i) {
        result[i] = st.top();
        st.pop();
    }
    
    return result;
}

Time Complexity

The time complexity of this solution is O(n), where n is the number of elements in the asteroids vector. Each asteroid is processed at most twice: once when pushed and possibly once when it causes collisions (some asteroids might even explode), making it an efficient solution.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI