Daily LeetCode Problems: Problem 735: Asteroid Collision

Solving LeetCode Problem 735: Asteroid Collision

Welcome to another daily article on LeetCode problems! In today’s article, we will delve into problem 735, “Asteroid Collision”. We will carefully examine the problem statement, discuss an approach to solving it, provide pseudocode for the solution, and discuss some implementation details. Let’s dive in!

Problem Statement

The problem requires us to simulate the collision of asteroids moving in a row. Each asteroid in the array asteroids has an integer value representing its size, and the sign represents its direction. Positive values represent asteroids moving to the right, and negative values represent asteroids moving to the left. If two asteroids collide, the smaller one will explode. If both asteroids are of the same size, both will explode. Asteroids moving in the same direction will never collide.

Our task is to find out the state of the asteroids after all collisions.

Approach

To simulate the asteroid collisions, we will use a stack data structure. The stack will help us keep track of the asteroids that have not yet collided. We will iterate through each asteroid and perform the following steps:

1. If the stack is empty or the current asteroid is moving to the right (positive value), push it onto the stack.
2. If the current asteroid is moving to the left (negative value), we need to check for collisions with the asteroids in the stack.

• While the stack is not empty and the top asteroid in the stack is moving to the right (positive value) and its absolute value is less than the current asteroid’s absolute value, pop the asteroid from the stack as it will explode.
• If there is an asteroid in the stack moving to the right with the same absolute value as the current asteroid, pop it from the stack as both will explode.
• If there is an asteroid in the stack moving to the right with a greater absolute value, the current asteroid will explode, and we continue to the next asteroid.

1. After iterating through all asteroids, the stack will contain the remaining asteroids that have not collided. They represent the state of the asteroids after all collisions.

Pseudocode

Let’s express the solution steps in pseudocode:

function asteroidCollision(asteroids):
    Initialize an empty stack.

    For each asteroid in asteroids:
        If the stack is empty or the current asteroid is moving to the right (positive value):
            Push the current asteroid onto the stack.
        Else (current asteroid is moving to the left, negative value):
            While the stack is not empty and the top asteroid in the stack is moving to the right and has a smaller absolute value:
                Pop the asteroid from the stack as it will explode.

            If there is an asteroid in the stack moving to the right with the same absolute value:
                Pop it from the stack as both will explode.

            If there is an asteroid in the stack moving to the right with a greater absolute value:
                The current asteroid will explode, and we continue to the next asteroid.

    The stack now contains the remaining asteroids that have not collided.
    Return the stack as the state of the asteroids after all collisions.

Implementation Details

Implementing the asteroidCollision function in your preferred programming language should be straightforward. You can use a stack data structure to keep track of the asteroids that have not collided. Remember to handle edge cases, such as when the array asteroids is empty.

Full Solution

Python

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

    for a in asteroids:
      if a > 0:
        stack.append(a)
      else:  # a < 0
        # Destroy previous positive one(s).
        while stack and stack[-1] > 0 and stack[-1] < -a:
          stack.pop()
        if not stack or stack[-1] < 0:
          stack.append(a)
        elif stack[-1] == -a:
          stack.pop()  # Both explode.
        else:  # stack[-1] > current
          pass  # Destroy current, so do nothing.

    return stack

Java

class Solution {
  public int[] asteroidCollision(int[] asteroids) {
    Stack<Integer> stack = new Stack<>();

    for (final int a : asteroids)
      if (a > 0) {
        stack.push(a);
      } else { // a < 0
        // Destroy previous positive one(s).
        while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -a)
          stack.pop();
        if (stack.isEmpty() || stack.peek() < 0)
          stack.push(a);
        else if (stack.peek() == -a)
          stack.pop(); // Both explode.
        else           // stack.back() > current
          ;            // Destroy current, so do nothing.
      }

    return stack.stream().mapToInt(Integer::intValue).toArray();
  }
}

C++

class Solution {
 public:
  vector<int> asteroidCollision(vector<int>& asteroids) {
    vector<int> stack;

    for (const int a : asteroids)
      if (a > 0) {
        stack.push_back(a);
      } else {  // a < 0
        // Destroy previous positive one(s).
        while (!stack.empty() && stack.back() > 0 && stack.back() < -a)
          stack.pop_back();
        if (stack.empty() || stack.back() < 0)
          stack.push_back(a);
        else if (stack.back() == -a)
          stack.pop_back();  // Both explode
        else                 // stack.back() > current
          ;                  // Destroy current, so do nothing
      }

    return stack;
  }
};

Conclusion

In this article, we explored LeetCode problem 735, “Asteroid Collision”. We carefully examined the problem statement, discussed an approach using a stack to simulate the asteroid collisions, provided pseudocode for the solution, and discussed some implementation details.

Remember, consistent practice and problem-solving are essential for enhancing your coding skills. So, make it a habit to challenge yourself with more LeetCode problems regularly. Happy coding!