grid47 Exploring patterns and algorithms
Aug 25, 2024
6 min read
Solution to LeetCode 735: Asteroid Collision Problem
You are given an array of integers representing asteroids in a row. Each asteroid has a size and a direction, with positive integers representing asteroids moving right and negative integers representing asteroids moving left. You need to determine the state of the asteroids after all collisions.
Problem
Approach
Steps
Complexity
Input: The input is an array of integers, where each integer represents an asteroid. A positive value means the asteroid is moving to the right, and a negative value means it is moving to the left.
Example: asteroids = [10, 15, -10]
Constraints:
• 2 <= asteroids.length <= 10^4
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0
Output: Return the final state of the asteroids after all collisions, as an array of integers.
Example: For the input [10, 15, -10], the output should be [10, 15].
Constraints:
Goal: Determine the final state of the asteroids after resolving all collisions.
Steps:
• Iterate through the array of asteroids.
• Use a stack to track the current state of the asteroids.
• For each new asteroid, check if it will collide with the top of the stack (which represents the asteroid moving to the right).
• If a collision occurs, resolve it by removing the smaller asteroid or both if they are of equal size.
• If no collision occurs, push the asteroid onto the stack.
Goal: The grid size and asteroid values are constrained to avoid overflow and ensure efficiency.
Steps:
• The number of asteroids will be between 2 and 10^4.
• Each asteroid's value will be between -1000 and 1000.
• The asteroid values are non-zero integers.
Assumptions:
• All asteroids move at the same speed.
• Two asteroids moving in the same direction will not collide.
• Input: Starting with asteroids [10, 15, -10], the asteroid 15 collides with -10, leaving 15 intact. The final state is [10, 15].
• Explanation: The 15 asteroid moves to the right, while -10 moves to the left. Since 15 is larger than -10, it survives, and -10 explodes. The 10 and 15 do not collide, so they remain.
Approach: Use a stack to simulate the movement and collision of the asteroids.
Observations:
• Each time an asteroid moves right, we need to check if it will collide with the one moving left.
• We can track the state of the asteroids with a stack, where we only need to check the top of the stack for potential collisions.
Steps:
• Initialize an empty stack.
• For each asteroid in the input array, check if it collides with the asteroid at the top of the stack.
• If a collision occurs, remove the top of the stack or both asteroids if they have equal size.
• Otherwise, push the asteroid onto the stack.
Empty Inputs:
• No empty input arrays will be provided, as the minimum length of the array is 2.
Large Inputs:
• The algorithm should handle large inputs up to the maximum size (10^4 elements).
Special Values:
• If all asteroids are moving in the same direction, the result will be the same array as input.
Constraints:
• The solution must be efficient to handle up to 10^4 elements.
vector<int> asteroidCollision(vector<int>& ast) {
int dir =0, n = ast.size();
vector<int> stk;
for(inta : ast) {
bool eq =false;
while(!stk.empty() && (((double)stk.back()/a) <0&& a <0) && (abs(stk.back()) < abs(a))) {
stk.pop_back();
}
if(!stk.empty() && (stk.back() ==-a && a <0)) {
// cout << stk.back();
stk.pop_back();
continue;
}
if (stk.empty() || ((double)stk.back()/a >0) || ((double)stk.back()/a <0&& a >0))
stk.push_back(a);
}
return stk;
}
1 : Initialization
vector<int> asteroidCollision(vector<int>& ast) {
Define the function that accepts an array of asteroids as input.
2 : Variable Declaration
int dir =0, n = ast.size();
Initialize direction (`dir`) and get the size of the asteroid array (`n`).
3 : Stack Initialization
vector<int> stk;
Declare an empty stack (`stk`) to manage the asteroids during the collision simulation.
4 : Loop
for(inta : ast) {
Iterate through each asteroid in the input array.
5 : Flag Initialization
bool eq =false;
Initialize a flag `eq` to track whether a collision has occurred for the current asteroid.
6 : Collision Check
while(!stk.empty() &&
Check if the stack is non-empty and if there is a potential for collision between the current asteroid and the last asteroid in the stack.
7 : Collision Condition
(((double)stk.back()/a) <0&& a <0) &&
Check if the last asteroid in the stack is moving to the right and the current one is moving to the left.
8 : Collision Condition
(abs(stk.back()) < abs(a))) {
Ensure the current asteroid is larger than the one in the stack (by comparing absolute values).
9 : Pop Asteroid from Stack
stk.pop_back();
Remove the last asteroid from the stack, as it is destroyed by the current one.
10 : Same Size Collision
if(!stk.empty() && (stk.back() ==-a && a <0)) {
Check if the current asteroid collides with an asteroid of the same size but moving in the opposite direction.
11 : Pop Matching Asteroid
stk.pop_back();
Remove the matching asteroid from the stack, as both asteroids are destroyed in the collision.
12 : Continue
continue;
Skip the current asteroid as it has been destroyed in the collision.
13 : Asteroid Push
if (stk.empty() || ((double)stk.back()/a >0) || ((double)stk.back()/a <0&& a >0))
If no collision occurs, or if the current asteroid moves in the opposite direction of the last asteroid in the stack, push it onto the stack.
14 : Stack Push
stk.push_back(a);
Push the current asteroid onto the stack.
15 : Return Result
return stk;
Return the stack, which contains the remaining asteroids after all collisions.
Best Case: O(n), where n is the number of asteroids, when no collisions occur.
Average Case: O(n), as each asteroid is processed once.
Worst Case: O(n), as in the worst case, all asteroids could potentially collide.
Description: The algorithm runs in linear time because each asteroid is either pushed to or popped from the stack once.
Best Case: O(1), if there are no collisions and the stack remains empty.
Worst Case: O(n), where n is the number of asteroids, as the stack may store all asteroids in the worst case.
Description: The space complexity is proportional to the number of asteroids due to the stack storing the results.
