Sponsored
Sponsored
This approach leverages a stack data structure to resolve collisions. We maintain a stack to keep track of the rightward-moving asteroids and resolve them when encountering leftward-moving asteroids. If the stack is empty or the asteroid is moving right, simply push it onto the stack. When encountering a leftward-moving asteroid, compare it to the stack's top. If the sizes are equal, both asteroids explode; if the stack's top is smaller, the stack's top asteroid explodes; otherwise, the current leftward-moving asteroid does not survive. Iterate through the entire list with these rules to achieve the desired result.
Time Complexity: O(n). Each asteroid is pushed and popped from the stack at most once.
Space Complexity: O(n). In the worst case, all asteroids are moving in the same direction and are all stored in the stack.
1def asteroidCollision(asteroids):
2 stack = []
3 for ast in asteroids:
4 while stack and ast < 0 < stack[-1]:
5 if stack[-1] < -ast:
6 stack.pop()
7 continue
8 elif stack[-1] == -ast:
9 stack.pop()
10 break
11 else:
12 stack.append(ast)
13 return stackThe function asteroidCollision initializes an empty list as a stack. It iterates over each asteroid and checks for a collision condition and resolves it by comparing the stack's top value with the current asteroid. Depending on the conditions, it either pops from the stack or appends to it while iterating through the entire list.
This method involves using two pointers to manage the movement of asteroids in the array, with no additional stack usage. Although usually less intuitive than a stack approach, the two-pointer solution iteratively resolves collisions simultaneously moving both pointers forward and backward depending on conditions. However, a true two-pointer solution for asteroid collisions is typically not the ideal choice here compared to a stack-based method in terms of simplicity and efficiency.
Time Complexity: O(n) due to a single pass through the array.
Space Complexity: O(n) for potential stack usage in storing results.
1#include <vector>
2using namespace std;
3
4vector<int> asteroidCollision(vector<int>& asteroids) {
5 vector<int> stack;
for (int ast : asteroids) {
while (!stack.empty() && ast < 0 && stack.back() > 0) {
if (stack.back() < -ast) {
stack.pop_back();
continue;
} else if (stack.back() == -ast) {
stack.pop_back();
}
break;
}
if (stack.empty() || ast > 0 || stack.back() < 0) {
stack.push_back(ast);
}
}
return stack;
}The C++ solution here shares the same logic as the Python one, accomplishing control flow via a stack vector and resolving asteroid collisions by evaluating conditions during traversal.