Ever been intrigued by the question "Explain the asteroid collision?" during an interview? In this blog, we will discuss an interview question that has been asked by company giants like Amazon, Google, and other product-based companies called "Asteroid Collision."
The approach and algorithm will be discussed in detail, along with the code in C++.
Problem Statement
The formal problem statement for Asteroid Collision is as follows:
You are given an array of "ASTEROIDS" representing asteroids in a row. For each element of the given array, its absolute value denotes the size of that asteroid. Its sign denotes the direction it is moving. If it's positive, it's moving to the right; if it's negative, it's moving to the 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 asteroids get destroyed. Two asteroids moving in the same direction never collide. What will be the final states of the asteroids after collision?
Example
Input
{2, 4, 1, -4}
You can also try this code with Online C++ Compiler
The first three asteroids will not collide with each other since all are moving in the same direction. The fourth asteroid is coming in the opposite direction and hence will collide with the third asteroid. The smaller one will get destroyed. Now, the fourth asteroid will collide with the second asteroid, and both will get destroyed since they are the same in magnitude. Hence only one asteroid will left, i.e. {2}.
Hence, after the collision, the state of the asteroids will be {2}.
Without further ado, let's start figuring out the solution for this.
Before delving into the asteroid collision algorithm, let's see the observations that will serve as the foundation for our solution:
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 asteroids get destroyed.
The collision of two asteroids travelling in the same direction is impossible.
You are supposed to find the state of the asteroids after all collisions.
An asteroid that moves toward the left will never collide if there is no asteroid before it moves to the right.
An asteroid moving toward the rightwill never collide if there is no asteroid after itmoves to the left.
Stack as a data structure can be beneficial when the sequence of events matters. They help ensure that a system doesn't do the previous action before moving on to the next. Therefore, use the idea of the stack to maintain the state of the asteroids. Now, if we find an asteroid moving to the left (negative value), at index i, it will collide with an asteroid moving to the right, which is of positive value and has an index less than i.
Hence, the stack will help keep track of asteroids moving to the right and then pop the elements from the stack as and when any asteroid gets destroyed.
Algorithm
The algorithm is as follows:
Define a stack for tracking asteroids, say the remaining asteroids.
Define an array and then Iterate through the array containing the asteroids having current index i.
If the asteroids[i] is positive, push the current element into the stack.We shall push the current element onto the stack if it is not empty or if the element at the top is negative. All the asteroids in the stack, including the current asteroid, would be travelling to the left since the asteroid at the top of the stack is negative. Thus, the current asteroid will not collide with any other asteroid.
As long as the top element is positive and smaller than the absolute value of asteroids[i], we shall continue to pop it off the stack if asteroids[i] is negative. 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, in the case of asteroids of equal size, both asteroids will be destroyed.
Otherwise, if the stack is empty or the top element is negative, we will push the current element into the stack.
Return all the elements of the stack showing the final state.
Dry run
The first three asteroids are moving in the same direction, so they will not collide.
Collision 1
The fourth asteroid is coming in the opposite direction and hence will collide with an asteroid of magnitude 1. The third asteroid will get destroyed.
Collision 2
Now the fourth asteroid will collide with the second asteroid. Since the size of both asteroids colliding with each other is the same. They destroy each other, leaving only the first asteroid.
C++ Implementation
#include<bits/stdc++.h>
using namespace std;
vector < int > collidAst(int asteroids[], int n) {
//Maintaining a stack
stack < int > asteroidsLeft;
/*
Iterate the array and on
a condition
Insert the currently selected
asteroid into a stack
*/
for (int i = 0; i < n; i++) {
if (asteroids[i] > 0 || asteroidsLeft.size() == 0 || asteroidsLeft.top() < 0) {
asteroidsLeft.push(asteroids[i]);
}
else {
//Pop Asteroids
while (asteroidsLeft.size() > 0 && asteroidsLeft.top() > 0 && asteroidsLeft.top() < -asteroids[i]) {
asteroidsLeft.pop();
}
/*
Size of asteroid1 = asteroid2
therefore destroy both
*/
if (asteroidsLeft.size() > 0 && asteroidsLeft.top() == -asteroids[i]) {
asteroidsLeft.pop();
}
/*
Current asteroid is not destroyed,
then push the current asteroid
to the stack
*/
else if (asteroidsLeft.size() == 0 || asteroidsLeft.top() <= 0) {
asteroidsLeft.push(asteroids[i]);
}
}
}
/*
Creation of a vector
to store the answer
*/
vector < int > result;
while (asteroidsLeft.size() != 0) {
result.push_back(asteroidsLeft.top());
asteroidsLeft.pop();
}
//Reverse the vector.
reverse(result.begin(), result.end());
//Return the final state
return result;
}
int main() {
int asteroids[] = {2, 4, 1, -4};
int n = sizeof(asteroids) / sizeof(int);
cout << "Initial state of asteroids:";
for (int i = 0; i < n; i++) {
cout << asteroids[i] << " ";
}
cout << endl;
/*
Making a function call to get
the answer.
*/
vector < int > v = collidAst(asteroids, n);
cout << "Final state of asteroids after the collision:";
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << endl;
}
You can also try this code with Online C++ Compiler
Let us see the user function template for asteroid collision using python 3
def asteroidCollision(asteroids):
res = []
print("Initial state of asteroids: ",asteroids)
for asteroid in asteroids:
while res and asteroid < 0 < res[-1]:
if res[-1] < -asteroid:
res.pop()
continue
elif res[-1] == -asteroid:
res.pop()
break
else:
res.append(asteroid)
return res
print("Final state of asteroids after the collision: ", asteroidCollision([2, 4, 1, -4]))
You can also try this code with Online C++ Compiler
The measure of computational complexity known as "time complexity" specifies how long it takes a computer to execute an algorithm.
The asteroid collision has an O(N) time complexity, where N is the array's length.
We are iterating through the given array, which will take O(N) time. Also, we are performing push and pop operations on a stack that takes constant time.
Space Complexity
The total size of an algorithm's space consumption relative to the size of its input is referred to as space complexity.
The space complexity of the asteroid collision is O(N). Here, N is the length of the 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."
C++ is used to create browsers, operating systems, and apps, as well as in-game programming, software engineering, data structures, and other applications.
What is a FIFO data structure?
FIFO means "First In, First Out." In the stack data structure, the first-in, first-out structure is where the data inserted first is popped out first.
What is the time complexity for inserting an element in a map?
The insertion complexity for an element is O(logN) when only the element is to be inserted and when the position is also available, it is O(1).
How do stacks work?
A stack, sometimes known as a "push-down stack," is an organized group of objects where new items are constantly added to and removed from the stack from the same end. The term "top" is frequently used to describe this finish. The "base" is the end that faces the top.
What does the term "collision" mean?
A collision happens when several values are to be hashed by a specific hash function hash to the exact position in the table or data structure the hash function is creating.
Conclusion
The article discussed "Asteroid Collision," a popular interview question that has been asked multiple times at 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.
116+ registered 