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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Asteroid Collision

Number: 735

Difficulty: Medium

Paid? No

Companies: Amazon, Meta, Google, Microsoft, Dream11, Goldman Sachs, PhonePe, Accolite, OpenAI, Oracle, TikTok, Flipkart, DoorDash, Qualtrics, Bloomberg, Nvidia, Salesforce, Adobe, Sprinklr, Deutsche Bank, IMC, Apple, Citadel, SoFi, Roku, ServiceNow, Uber

Problem Description

Given an array of integers where each integer represents an asteroid (its absolute value for size and sign for direction: positive for right-moving and negative for left-moving), simulate all collisions between asteroids. When two asteroids meet, the smaller one explodes; if they are equal in size, both explode. Asteroids moving in the same direction never collide. Return the final state of the asteroids after all possible collisions.

Key Insights

  • Use a stack to keep track of the surviving asteroids.
  • Only a collision happens when a right-moving asteroid (positive) is on the stack and a left-moving asteroid (negative) is encountered.
  • Compare the absolute values to decide if one or both asteroids explode.
  • Continue processing collisions until no further collisions are possible with the current asteroid.

Space and Time Complexity

Time Complexity: O(n) where n is the number of asteroids, since each asteroid is pushed and popped at most once. Space Complexity: O(n) in the worst case, when no collisions occur and all asteroids remain on the stack.

Solution

The solution uses a stack to simulate the asteroid collision process. For each asteroid in the input:

  • If it is moving to the right or the stack is empty, simply add it to the stack.
  • If it is moving to the left, check the asteroid on top of the stack:
    • If the top asteroid is moving to the right, they might collide.
    • Compare sizes:
      • If the left-moving asteroid is larger (in absolute terms), pop the stack and continue checking.
      • If both are equal, pop the stack and do not add the current asteroid.
      • If the right-moving asteroid is larger, the current asteroid explodes.
  • If no collision occurs for the current asteroid, push it onto the stack. Finally, the stack represents the surviving asteroids order.

Code Solutions

# Function to simulate asteroid collisions
def asteroidCollision(asteroids):
    # Initialize an empty list as a stack to hold surviving asteroids
    stack = []
    # Iterate through each asteroid in the input list
    for ast in asteroids:
        # Flag to check if the current asteroid has exploded
        exploded = False
        # Check for potential collision while there is an asteroid in stack and a collision condition holds (right-moving on stack and left-moving current)
        while stack and ast < 0 and stack[-1] > 0:
            # If the incoming left-moving asteroid is larger than the right-moving one on stack, pop the top and continue checking
            if abs(ast) > abs(stack[-1]):
                stack.pop()
                continue  # Continue the loop to check next potential collision
            # If they are equal, both explode: pop the stack and mark explosion, break the loop
            elif abs(ast) == abs(stack[-1]):
                stack.pop()
            # Mark the incoming asteroid as exploded and break out of the loop
            exploded = True
            break
        # If the asteroid did not explode during collisions, push it onto the stack
        if not exploded:
            stack.append(ast)
    # Return the surviving asteroids
    return stack

# Example usage:
# print(asteroidCollision([5,10,-5]))  # Output: [5,10]
← Back to All Questions