Asteroid Collision LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Bloomberg ByteDance Citadel DE Shaw DoorDash Facebook Flipkart Goldman Sachs Google lyft Microsoft Oracle Robinhood Salesforce Uber
Hotstar tiktokViews 6710

Problem Statement

Asteroid Collision LeetCode Solution – 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.

Asteroid Collision LeetCode Solution

Example

Test Case 1:

Input:

asteroids = [5, 10, -5]

Output:

[5, 10]

Explanation:

The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Approach:

Intuition

According to the question, positive values are moving to the right and negative values are moving to the left. We can apply the concept of relative velocity and make positive values as fixed and negative values now moving with double velocity in the negative direction. But, the magnitude of velocity does not matter only the direction matters.

Idea

Let’s consider an example:-

[8, 9, 6, -7, -9, 12, 50, -34]

Start iterating from the beginning. Whenever we encounter a positive value, we don’t have to do anything. Since they are fixed, they won’t attack anyone. But the moment we see a negative value, we are sure it is going to attack positive values.

Imagine [8, 9, 6] are happily sitting inside the array. The moment -7 enters, it will start knocking out positive values. This gives an idea we can use a stack to solve this problem.

Let’s see how to use this idea to code.

Consider the same example [8, 9, 6, -7, -9, 12, 50, -34]
Initially i = 0.

  1. Whenever we encounter a positive value, we will simply push it to the stack.
  2. The moment we encounter a negative value, we know some or all or zero positive values will be knocked out of the stack. The negative value may itself be knocked out or it may enter the stack.
    We will keep on popping the elements from the stack while the asteroids[i] > s.top(). But remember, negative asteroids can never pop another negative asteroid since they will never meet them. So, the final condition is while(!s.empty() and s.top() > 0 and s.top() < abs(ast[i])), we will pop the elements.
  3. We have to take care of the case when s.top() == asteroids[i]. In this case, one positive element will pop out and a negative asteroid won’t enter the stack.
  4. If after knocking out elements stack becomes empty() or s.top() becomes negative, that means the current asteroids[i] will enter the stack.

Code for Serialize and Deserialize Binary Tree

C++ Program

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& a) {
        vector<int> s; // use vector to simulate stack.
        for (int i = 0; i < a.size(); i++) {
            if (a[i] > 0 || s.empty() || s.back() < 0) // a[i] is positive star or a[i] is negative star and there is no positive on stack
                s.push_back(a[i]);
            else if (s.back() <= -a[i]) { // a[i] is negative star and stack top is positive star
                if(s.back() < -a[i]) i--; // only positive star on stack top get destroyed, stay on i to check more on stack.
                s.pop_back(); // destroy positive star on the frontier;
            } // else : positive on stack bigger, negative star destroyed.
        }
        return s;
    }
};

Java Program

class Solution {
    public int[] asteroidCollision(int[] a) {
        LinkedList<Integer> s = new LinkedList<>(); // use LinkedList to simulate stack so that we don't need to reverse at end.
        for (int i = 0; i < a.length; i++) {
            if (a[i] > 0 || s.isEmpty() || s.getLast() < 0)
                s.add(a[i]);
            else if (s.getLast() <= -a[i])
                if (s.pollLast() < -a[i]) i--;
        }
        return s.stream().mapToInt(i->i).toArray();
    }
}

Complexity Analysis for Asteroid Collision LeetCode Solution

Time Complexity: O(n). Gone n. Then traversed back n, and popped all stack.

Space Complexity: O(n). Stack size. All asteroids are on the stack.

Translate »