SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem involves a series of asteroids represented by an array. Each asteroid is moving either to the left (negative value) or to the right (positive value). When two asteroids collide, the one with a larger absolute value destroys the other. If they are equal in size, both asteroids are destroyed. The task is to simulate all the collisions and return the state of the asteroids after all collisions.

Intuition

The key insight is that collisions only happen between a right-moving asteroid and a left-moving asteroid. By maintaining a stack, we can effectively simulate the process of resolving collisions as we iterate through the asteroid list. Each time we encounter a collision, we resolve it by comparing the absolute sizes of the asteroids involved.

Approach

1. Initialize an empty stack to keep track of asteroids that have not been destroyed.
2. Iterate over the asteroids array:
   • If the stack is empty or the current asteroid is moving to the right (positive value), push it onto the stack.
   • If the current asteroid is moving to the left (negative value), check for possible collisions:
     • Continuously compare the current asteroid with the top of the stack:
       • If the top of the stack is moving to the right and is smaller in size, pop it from the stack (destroy it).
       • If the top of the stack is equal in size to the current asteroid, pop it from the stack, and discard the current asteroid.
       • If the top of the stack is larger, discard the current asteroid.
     • If no collision occurred, push the current asteroid onto the stack.
3. Return the stack, which now contains the remaining asteroids after all collisions have been resolved.

Complexity

Time Complexity:

O(n), where n is the number of asteroids. Each asteroid is pushed and popped from the stack at most once.

Space Complexity:

O(n) in the worst case, if all asteroids are stored in the stack.

Code

C++

class Solution {
public:
    std::vector<int> asteroidCollision(std::vector<int>& asteroids) {
        std::vector<int> res;
        for (int i = 0; i < asteroids.size(); ++i) {
            int cur = asteroids[i];
            while (!res.empty() && res.back() > 0 && cur < 0) {
                if (res.back() < -cur) {
                    res.pop_back();
                    continue;
                } else if (res.back() == -cur) {
                    res.pop_back();
                }
                cur = 0;
            }
            if (cur != 0) {
                res.push_back(cur);
            }
        }
        return res;
    }
};

Python

class Solution:
    def asteroidCollision(self, asteroids):
        res = []
        for cur in asteroids:
            while res and res[-1] > 0 and cur < 0:
                if res[-1] < -cur:
                    res.pop()
                    continue
                elif res[-1] == -cur:
                    res.pop()
                break
            else:
                res.append(cur)
        return res

Java

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int cur : asteroids) {
            boolean isDestroyed = false;
            while (!stack.isEmpty() && stack.peek() > 0 && cur < 0) {
                if (stack.peek() < -cur) {
                    stack.pop();
                    continue;
                } else if (stack.peek() == -cur) {
                    stack.pop();
                }
                isDestroyed = true;
                break;
            }
            if (!isDestroyed) {
                stack.push(cur);
            }
        }
        return stack.stream().mapToInt(i -> i).toArray();
    }
}

JavaScript

var asteroidCollision = function (asteroids) {
    const res = []
    for (let i = 0; i < asteroids.length; i++) {
        const last = res[res.length - 1]
        const cur = asteroids[i]
        if (!res.length || last < 0 || cur > 0) {
            res.push(cur)
        } else if (-cur == last) {
            res.pop()
        } else if (-cur > last) {
            res.pop()
            i--
        }
    }
    return res
};