735.Asteroid_Collision(Medium).md

735. Asteroid Collision (Medium)

Date and Time: Oct 24, 2024, 14:02 (EST)

Link: https://leetcode.com/problems/asteroid-collision/

Question:

We 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 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.

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.

Edge case1:

Input: asteroids = [8, 8]
Output: [8, 8]
Explanation: They are in the same direction.

Edge case2:

Input: asteroids = [-2, -2, -1, -2]
Output: [-2, -2, -1, -2]
Explanation: They are in the same direction.

Edge case3:

Input: asteroids = [-2, -1, 1, 2]
Output: [-2, -1, 1, 2]
Explanation: If one go to the left, another go to the right, they will not collide.

Constraints:

• 2 <= asteroids.length <= 10^4

• -1000 <= asteroids[i] <= 1000

• asteroids[i] != 0

Walk-through:

1. First we check if the last asteroid > 0 and current asteroid < 0, if so, this is the case when collision could happen. (Note: the another way around will not collide, because one go to the left, one go to the right.)

2. Otherwise, we just append the asteroid into stack[].

3. If there could have a collision, we first check the difference. If diff < 0, that means the current asteroid is larger than the prev asteroid, and we should continuously check it. If diff == 0 that means both asteroid will explode, so we pop from stack[] and break the while loop. Lastly, if diff > 0 that means the last asteroid is larger than the current one, so we just break the while loop.

Python Solution:

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        # if stack[-1] > 0 and asteroids[i] < 0, only case when collision could happen
        # Otherwise, append asteroid into stack
        # calculate the abs diff between the last asteroid and current asteroid
        # if diff < 0, last asteroid explodes and continue comparing
        # if diff == 0, both explode
        # if diff > 0, the new asteroid explodes

        # TC: O(n), SC: O(n)
        stack = []
        for a in asteroids:
            # Check the case when collision could happen
            while stack and stack[-1] > 0 and a < 0:
                diff = abs(stack[-1]) - abs(a)
                if diff < 0:
                    stack.pop()
                elif diff == 0:
                    stack.pop()
                    break
                else:
                    break
            else:
                stack.append(a)
        
        return stack

Time Complexity: $O(n)$
Space Complexity: $O(n)$