Скачать или смотреть Lyft Coding Interview Question - Asteroid Collision

Here is a step by step explanation of a coding question involving a stack!

Check out my interview prep platform for learning the patterns!
📢 Interview Prep Platform: https://algoswithmichael.com

🎧 Join the community Discord:   / discord  
💰 Support me on Patreon:   / michaelmuinos  
🔗Follow me on LinkedIn:   / michael-muinos  
📂Follow me on Github: https://github.com/MichaelMuinos

Asteroid collision is a popular Lyft coding interview question that involves the use of a stack. We are given an integer array containing positive and negative numbers where positive numbers move right and negative numbers move left. Each asteroid moves at the same speed, thus we need to determine which asteroids will collide with each other and which ones will come out on top. It is vital to understand that we only need to check pairings of numbers that have a positive number on the left side and negative number on the right side. If this scenario is occurring, the asteroids will for sure collide and we must have logic in place to handle it.

The way we solve this problem is using a stack. We iterate over our input array and if the number is a positive number, if our stack is empty, or the last number in the stack is a negative number, then we can immediately add the number into the stack. If those statements are not true, that means that the last number on the stack is a positive number and we need to compare the current number we are looking at to determine which asteroid will win. If the ABS(our current number) is greater than the last element on the stack, we will pop from the stack. We will continuously do this until the stack is empty, the current asteroid gets beat by another asteroid, or it arrives at a negative number in the stack.

One edge case we must consider is when the numbers on the left and right are the same. In this scenario, both the asteroids will be removed from our output array. The time complexity of our solution is O(N) where N is the number asteroids we have and our space complexity is O(N) because in the worst case we must add every asteroid from our input inside of our stack.