Asteroid Collision (Tekion Frontend Interview) | Problem Solving Round

Concepts

This problem can be effectively solved using a stack data structure. The stack allows us to simulate the collision process by pushing and popping asteroids as they collide. The intuition behind using a stack is that it operates in a Last In First Out (LIFO) manner, which is ideal for this problem where we need to evaluate asteroids as they encounter each other sequentially.

Problem Breakdown

Solution

Below is a JavaScript implementation of the algorithm described:

JavaScript(collision.js)
Copy
function asteroidCollision(asteroids) {
    const stack = [];

    for (const asteroid of asteroids) {
        let alive = true;

        while (alive && asteroid < 0 && stack.length > 0 && stack[stack.length - 1] > 0) {
            const top = stack[stack.length - 1];

            if (Math.abs(asteroid) > top) {
                // The current asteroid is larger, pop the top
                stack.pop();
            } else if (Math.abs(asteroid) === top) {
                // Both asteroids are equal, pop and do not push
                stack.pop();
                alive = false; // Current asteroid is destroyed
            } else {
                // The asteroid on the stack is larger, do not add current asteroid
                alive = false; 
            }
        }

        if (alive) {
            stack.push(asteroid); // Push the current asteroid if it's still alive
        }
    }

    return stack; // Return the final array of asteroids
}

// Example usage:
const asteroids = [5, 8, -10, -7];
const result = asteroidCollision(asteroids);
console.log(result); // Output: [-10, -7]

Conclusion

The stack-based approach effectively handles the asteroid collision problem by maintaining the state of surviving asteroids throughout the process. By carefully evaluating each asteroid against the last one added to the stack, we can efficiently resolve collisions and return the final array. This method not only solves the problem neatly but also demonstrates the power of using stacks for specific algorithmic challenges.

Similar Questions

• Evaluate Reverse Polish Notation
• Implement a Queue using Stacks
• Parentheses Matching Problem
• Next Greater Element using a Stack