Asteroid Collision

Pranchal Agrahari
Last Updated: May 13, 2022

Introduction

In this blog, we will be discussing an interview question asked in amazon, google, and other big product-based companies called “Asteroid Collision.” We will be discussing the approach and algorithm in detail, along with the code in C++. But before moving on to the solution, let’s understand the problem statement 

Problem Statement

The formal problem statement for Asteroid Collision is as follows:

You are given an array “ASTEROIDS” representing asteroids in a row. For each element of the given array, its absolute value denotes the size of that asteroid, and its sign denotes the direction it is moving in(+ve meaning right and -ve meaning left).

All asteroids are moving at the same speed. Whenever two asteroids collide, the smaller asteroid gets destroyed. If both the asteroids have the same size, then both the asteroids get destroyed. Two asteroids moving in the same direction never collide.

You are supposed to find the state of the asteroids after all collisions.

For Example :

Input: {3,-2,4}

Output: {3,4}

The first asteroid will destroy the second asteroid. Hence, after the collision, the state of the asteroids will be {3,4}.

 

 

Without any further ado, let’s get started to figure out the solution for this.

Recommended: Please solve it on CodeStudio first before moving on to the solution.

Asteroid Collision: Algorithm

Before discussing the algorithm, I would like to draw your attention to two very interesting observations that would make a base for our approach. The observations are as follows.

  • An asteroid that moves towards the left will never collide if there is no asteroid before it moving to the right.
  • An asteroid moving towards the right will never collide if there is no asteroid after it moving to the left.

 

The idea is to use the stack to maintain the state of the asteroids. If we find an asteroid moving to the left (-ve value), let’s say at index i, then it will collide with an asteroid moving to the right (+ve value) and having an index less than i. Hence, we can use a stack to keep track of asteroids moving to the right and then pop the elements from the stack as and when any asteroid gets destroyed.

 

The steps are as follows :

 

  • Define a stack for keeping track of asteroids, let’s say remaining Asteroids.

 

  • Iterate through the given array. Let’s say our current index is i.

 

  • If the ASTEROIDS[i] is positive, then we will push the current element into the stack.

 

  • If the stack is empty or the element at the top of the stack is negative, then also we will push the current element into the stack. Since the asteroid at the top of the stack is negative, all the asteroids in the stack and the current asteroid would be moving to the left. Thus, the current asteroid will not collide with any other asteroid.

 

  • If ASTEROIDS[i] is negative then while the element at the top of the stack is positive and is less than the absolute value of ASTEROIDS[i] we will keep popping the top element from the stack. We do this because the current asteroid will collide with and destroy all asteroids moving to the right and having a smaller size than the current asteroid.

 

  • Now, if the element at the top of the stack is equal to the absolute value of ASTEROIDS[i], then pop the element because incase of asteroids of equal size, both the asteroids will be destroyed.

 

  • Else if the stack is empty or the top element is negative, then we will push the current element into the stack.

 

  • Now all the elements present in the stack will represent the final state of the asteroids. Hence we will return all the elements of the stack.

Implementation

Below is code in c++ for the approach discussed above.

 

Code:

#include<bits/stdc++.h>
using namespace std;


vector<int> collidingAsteroids(int asteroids[],int n)
{
    
    // stack to keep track of remaining asteroids.
    stack<int> remainingAsteroids;

    //    Iterate through the given array
    for (int i = 0; i < n; i++)
    {
        //    Push the current asteroid in the stack.
        if (asteroids[i] > 0 || remainingAsteroids.size() == 0 || remainingAsteroids.top() < 0)
        {
            remainingAsteroids.push(asteroids[i]);
        }
        else
        {
            //    Pop the asteroids from the stack.
            while (remainingAsteroids.size() > 0 && remainingAsteroids.top() > 0 && remainingAsteroids.top() < -asteroids[i])
            {
                remainingAsteroids.pop();
            }

            //    If the size of both asteroids is the same, then destroy both the asteroids.
            if (remainingAsteroids.size() > 0 && remainingAsteroids.top() == -asteroids[i])
            {
                remainingAsteroids.pop();
            }

            //    If the current asteroid has not been destroyed then push the current asteroid to the stack.
            else if (remainingAsteroids.size() == 0 || remainingAsteroids.top() <= 0)
            {
                remainingAsteroids.push(asteroids[i]);
            }
        }
    }
  // creating a vector to store the answer.
    vector<int>ans;
    while(remainingAsteroids.size()!=0)
    {
        ans.push_back(remainingAsteroids.top());
        remainingAsteroids.pop();
    }
    //The elements stored in array are reversed in order so we need to reverse the vector

    reverse(ans.begin(),ans.end());

    //    Return the final state of the asteroids
    return ans;
}
int main()
{
    int asteroids[]={3,-2,4};
    int n=sizeof(asteroids)/sizeof(int);

    cout<<"State of asteroids before collision :";
    for(int i=0;i<n;i++)
    {
        cout<<asteroids[i]<<" ";
    }
    cout<<endl;

    // making function call to get the answer.
    vector<int> v=collidingAsteroids(asteroids,n);

    cout<<"Final state of asteroids after collision:";
    for(int i=0;i<v.size();i++)
    {
        cout<<v[i]<<" ";
    }
    cout<<endl;

}

 

Output:

State of asteroids before collision :3 -2 4 
Final state of asteroids after collision :3 4 

 

Time Complexity

O(N), where N is the length of the given array

We are iterating through the given array, which will take O(N) time. Also, we are performing push and pop operations on a stack which take constant time. Thus, the overall time complexity is O(N).

 

Space Complexity

O(N), where N is the length of the given array.

We are using a stack for maintaining the state of the asteroids, in the worst case when all the asteroids are moving in the same direction the size of the stack will become ‘N.’ Thus, the overall space complexity will be O(N).

Key Takeaways

The article discussed “Asteroid Collision,” a popular interview question that has been asked multiple times in companies like Amazon, Microsoft, and Google. We discussed the asteroid collision problem in detail with algorithms and code in c++ along with the complexity analysis of the code.

If you want to solve more problems like this which have been asked in the interviews, big tech giants like Amazon, Flipkart, Google, and Facebook, you can look out for interview problems at Code Studio.

If you are a beginner in coding and want to learn DSA, then you can look out for our guided path for DSA, which is absolutely free!

 

Happy Learning! 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think