algoadvance

You 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 for right, negative for 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.

Example 4:

Input: asteroids = [-2, -1, 1, 2]
Output: [-2, -1, 1, 2]
Explanation: The -2 and -1 are moving to the left, while the 1 and 2 are moving to the right. Asteroids moving the same direction never meet, so no collisions occur.

Clarifying Questions

  1. Can I assume that no two asteroids start at the same position?
    • Yes, each asteroid is represented by its size and direction, not position.
  2. What should be output if all asteroids explode?
    • Return an empty list [].
  3. Is the asteroid list non-empty?
    • Not necessarily, it could be empty, in which case you should return an empty list.

Strategy

  1. Use a stack to keep track of the ongoing asteroids.
  2. Iterate through each asteroid:
    • If the current asteroid is moving to the right (>0), push it onto the stack.
    • If it’s moving to the left (<0), compare it with the top element of the stack:
      • If the stack is empty or the top of the stack is also moving left or can’t collide (moving right auto), push the current asteroid onto the stack.
      • If a collision occurs (i.e., top of the stack is moving right), repeatedly pop from the stack (because the asteroids on the stack are smaller or will explode due to equal size) until: a. The stack is empty. b. The current left-moving asteroid is destroyed. c. The remaining top of the stack asteroid moving to the right is the winner.
  3. At the end, the stack will contain the remaining asteroids after all collisions.

Time Complexity

The time complexity is (O(n)) where (n) is the number of asteroids because each asteroid is processed at most once (pushed and popped from the stack).

Code

def asteroidCollision(asteroids):
    stack = []
    
    for asteroid in asteroids:
        while stack and asteroid < 0 < stack[-1]:
            if stack[-1] < -asteroid:
                stack.pop()
                continue
            elif stack[-1] == -asteroid:
                stack.pop()
            break
        else:
            stack.append(asteroid)
    
    return stack

# Example cases
print(asteroidCollision([5, 10, -5]))  # Output: [5, 10]
print(asteroidCollision([8, -8]))  # Output: []
print(asteroidCollision([10, 2, -5]))  # Output: [10]
print(asteroidCollision([-2, -1, 1, 2]))  # Output: [-2, -1, 1, 2]

This code follows the strategy and efficiently handles the asteroid collision as described in the problem statement.

Try our interview co-pilot at AlgoAdvance.com