We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Asteroid Collision

Difficulty: Medium

Problem Description

We are given an array asteroids of integers representing asteroids in a row. The indices of the asteroid 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.

Key Insights

  • Asteroids moving in the same direction do not collide.
  • A collision occurs when a positive asteroid meets a negative asteroid.
  • The outcome of a collision depends on the sizes of the colliding asteroids.
  • A stack can be used to efficiently manage the state of the asteroids as we process them.

Space and Time Complexity

Time Complexity: O(n) - Each asteroid is processed once. Space Complexity: O(n) - In the worst case, all asteroids could be stored in the stack.

Solution

To solve the problem, we can utilize a stack data structure. We iterate through each asteroid in the array. If the asteroid is positive, we simply push it onto the stack. If it's negative, we check for collisions with the top of the stack:

  1. If the top of the stack is also negative or the stack is empty, we push the negative asteroid onto the stack.
  2. If the top of the stack is positive, we have a collision:
    • Compare the absolute values of the top of the stack (positive asteroid) and the current (negative asteroid).
    • If the positive asteroid is larger, it remains; if the negative is larger, we discard the positive asteroid; if they are equal, both explode.

This approach maintains the state of the asteroids after all possible collisions.

Code Solutions

def asteroidCollision(asteroids):
    stack = []
    for asteroid in asteroids:
        while True:
            # If the asteroid is positive, push it onto the stack
            if asteroid > 0:
                stack.append(asteroid)
                break
            # If the stack is empty, or the top is negative, push the negative asteroid
            if not stack or stack[-1] < 0:
                stack.append(asteroid)
                break
            # Collision: compare sizes
            top = stack.pop()
            if top == -asteroid:  # Both explode
                break
            elif top > -asteroid:  # Positive asteroid survives
                stack.append(top)
                break
            # Negative asteroid survives
            # Do not push anything, continue checking with next asteroid
    return stack
← Back to All Questions