Leetcode 735. Asteroid Collision

Problem

Leetcode 735 - Asteroid Collision

Example:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Approach

Remind that any negative asteroid moves to left and any positive asteroid moves to right. So in a case where [-1, 1] the return array should still be [-1, 1].

We can use stack to solve this problem.

For each asteroid in the asteroids list, we can append it to stack.

Once stack has 2 or more elements there are 2 possibilities

• When asteroid2 is moving to right and asteroid1 is moving to left (because we’re popping from stack first asteroid that we pop from stack should be moving to left)
  • if asteroid1 + asteroid2 > 0:
    • we should append the positive asteroid
  • if asteroid1 + asteroid2 < 0:
    • we should append the negative asteroid
• Else put them back into stack

Visualization of the Approach:

asteroids = [5, 10, -5]
stack = []

stack = [5]

stack = [5, 10]
Since there are 2 elements in stack, we check if asteroid1 and asteroid2 are moving towards each other and since they're not, we ignore

stack = [5, 10, -5]
Since there are 2 elements in stack, we check if asteroid1 and asteroid2 are moving twoards each other and since they're, we compute asteroid1 + asteroid2 = 5.
Since it's a positivie number, we add the positive asteroid into stack

stack = [5, 10]
Since there are 2 elements in stack, we check if asteroid1 and asteroid2 are moving towards each other and since they're not, we ignore

Thus result = [5,10]

Here is the Python code for the solution:

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

        for a in asteroids:
            stack.append(a)

            if len(stack) >= 2:
                asteroid1 = stack.pop()
                asteroid2 = stack.pop()
                
                # if both asteroids are moving towards each other
                if asteroid1 < 0 and asteroid2 > 0:
                    # if the result is positive number, then we add positive asteroid
                    if asteroid1 + asteroid2 > 0:
                        stack.append(asteroid2)
                    # if the result is negative number, then we add negative asteroid
                    elif asteroid1 + asteroid2 < 0:
                        stack.append(asteroid1)
                    # in case of resulting 0, then we add nothing
                # if both asteroids are not moving towards each other then put it back into stack
                else:
                    stack.append(asteroid2)
                    stack.append(asteroid1)
                    break

        return stack

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$