Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

735. Asteroid Collision

Time: $O(n)$

Space: $O(n)$

			


class Solution {
 public:
  vector<int> asteroidCollision(vector<int>& asteroids) {
    vector<int> stack;

    for (const int a : asteroids)
      if (a > 0) {
        stack.push_back(a);
      } else {  // A < 0
        // Destroy previous positive one(s)
        while (!stack.empty() && stack.back() > 0 && stack.back() < -a)
          stack.pop_back();
        if (stack.empty() || stack.back() < 0)
          stack.push_back(a);
        else if (stack.back() == -a)
          stack.pop_back();  // Both explode
        else                 // Stack.back() > current
          ;                  // Destroy current, so do nothing
      }

    return stack;
  }
};




			


class Solution {
  public int[] asteroidCollision(int[] asteroids) {
    Stack<Integer> stack = new Stack<>();

    for (final int a : asteroids)
      if (a > 0) {
        stack.push(a);
      } else { // A < 0
        // Destroy previous positive one(s)
        while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -a)
          stack.pop();
        if (stack.isEmpty() || stack.peek() < 0)
          stack.push(a);
        else if (stack.peek() == -a)
          stack.pop(); // Both explode
        else           // Stack.back() > current
          ;            // Destroy current, so do nothing
      }

    return new ArrayList<>(stack).stream().mapToInt(i -> i).toArray();
  }
}




			


class Solution:
  def asteroidCollision(self, asteroids: List[int]) -> List[int]:
    stack = []

    for a in asteroids:
      if a > 0:
        stack.append(a)
      else:  # A < 0
        # Destroy previous positive one(s)
        while stack and stack[-1] > 0 and stack[-1] < -a:
          stack.pop()
        if not stack or stack[-1] < 0:
          stack.append(a)
        elif stack[-1] == -a:
          stack.pop()  # Both explode
        else:  # stack[-1] > current
          pass  # Destroy current, so do nothing

    return stack