How do you solve Asteroid Collision on LeetCode?

Asteroid Collision (LeetCode #735) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Asteroids moving in the same direction do not collide.

What is the brute force solution for Asteroid Collision?

The brute force approach for Asteroid Collision is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we simulate each collision by checking every pair of asteroids. If two asteroids collide, we determine the outcome based on their sizes and continue until no more collisions are possible. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Asteroid Collision?

Asteroid Collision uses the following concepts: Array, Stack, Simulation. The recommended patterns to study are: Stack, Simulation, Array.

What are the interview tips for Asteroid Collision?

Think about using a stack for problems involving last-in-first-out behavior. Always consider edge cases, such as when all asteroids collide. Explain your thought process clearly while coding.

What are common mistakes when solving Asteroid Collision?

Not handling the case where both asteroids are of equal size. Forgetting to update the index when elements are removed from the array.

#735

Asteroid Collision

Medium

ArrayStackSimulationStackSimulationArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Using a stack allows us to efficiently manage the collisions. We can push asteroids into the stack and handle collisions as we encounter them, ensuring we only process each asteroid once.

⚙️

Algorithm

5 steps

1Step 1: Initialize an empty stack to keep track of surviving asteroids.
2Step 2: Iterate through each asteroid in the array.
3Step 3: For each asteroid, check if it collides with the top of the stack (if the top is positive and the current is negative).
4Step 4: Resolve collisions by comparing sizes and updating the stack accordingly.
5Step 5: If no collision occurs, push the asteroid onto the stack.

solution.py15 lines

1# Full working Python code
2
3def asteroidCollision(asteroids):
4    stack = []
5    for asteroid in asteroids:
6        while stack and asteroid < 0 < stack[-1]:
7            if abs(asteroid) > abs(stack[-1]):
8                stack.pop()
9                continue
10            elif abs(asteroid) == abs(stack[-1]):
11                stack.pop()
12            break
13        else:
14            stack.append(asteroid)
15    return stack

ℹ

Complexity note: The time complexity is O(n) because each asteroid is processed once, and the stack operations (push/pop) are O(1). The space complexity is O(n) due to the stack storing the surviving asteroids.

1Asteroids moving in the same direction do not collide.
2Collisions only occur between a positive and a negative asteroid.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.