[LeetCode] 735. Asteroid Collision

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

2. Thoughts

Use stacks for left and right.
If left asteroid comes, compare with right and pop() or not.

need to take in care that left must survive when not right exists at stack.

3. Tips learned

3.1. Using "Else" with "While"

In Python, the else block after a loop (for or while) is executed only if the loop completes normally, without being terminated by a break statement. This can be particularly handy when the loop is used for searching or checking conditions, and you want to perform some action if the loop finishes without finding what it was looking for or triggering a break.
Sure, I'll provide some basic examples to illustrate how the while-else and for-else constructs work in Python.

Example: Searching in a List with a for-else Loop

Suppose you want to search for a specific element in a list and perform an action if the element is not found.

elements = [1, 2, 3, 4, 5]
search_for = 7

for element in elements:
    if element == search_for:
        print(f"Found {search_for}")
        break
else:
    print(f"{search_for} not found in the list")

In this example, if search_for is found in elements, the loop is exited with a break, and the else block is not executed. If the loop completes without finding search_for, the else block is executed.

4. My solution

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        lefts = []
        rights = []
        for asteroid in asteroids:
            # rights
            if asteroid > 0:
                rights.append(asteroid)

            # lefts
            else:
                flag = 0
                while len(rights) != 0:
                    if abs(asteroid) > rights[-1]:
                        rights.pop()
                    else:
                        if abs(asteroid) == rights[-1]:
                            rights.pop()
                        flag = 1
                        break
                if len(rights) == 0 and flag == 0:
                    lefts.append(asteroid)

        return lefts + rights

275/275 cases passed (82 ms)
Your runtime beats 96.96 % of python3 submissions
Your memory usage beats 78.53 % of python3 submissions (17.4 MB)

5. AI Solution and Improvements

Your solution to the asteroid collision problem is on the right track, but it can be simplified and made more efficient. Instead of maintaining two separate lists for left and right moving asteroids, you can use a single stack to keep track of the asteroids. When a new asteroid comes in, you only need to check its interaction with the top of the stack (the most recently added asteroid). Here are the steps:

1. Initialize an empty list to serve as a stack.
2. Iterate over each asteroid in the input list.
3. For each asteroid:
   • If the stack is empty or the current asteroid is moving to the right, add it to the stack.
   • If the current asteroid is moving to the left, check it against the top of the stack:
     • If the top of the stack is moving to the right, compare their sizes.
     • If the incoming asteroid is larger, pop the top of the stack and continue the comparison with the new top of the stack.
     • If they are equal, pop the top of the stack and discard the incoming asteroid.
     • If the incoming asteroid is smaller, discard it.
4. Repeat the process until all asteroids have been processed.

This approach is more efficient as it uses a single stack and minimizes the operations needed for each asteroid. Here is the improved Python code:

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []
        for asteroid in asteroids:
            while stack and asteroid < 0 < stack[-1]:
                if stack[-1] < -asteroid:
                    stack.pop()
                    continue
                elif stack[-1] == -asteroid:
                    stack.pop()
                break
            else:
                stack.append(asteroid)
        return stack

This code uses a while loop to handle the case where multiple right-moving asteroids may need to be popped from the stack for a single left-moving asteroid. The else block associated with the while loop ensures that the asteroid is only added to the stack if it doesn't collide with the previous ones. This makes the code more concise and efficient.