Loading problems...
TL;DR: Use a stack to maintain the state of asteroids moving right, resolving collisions immediately when a left-moving asteroid is encountered by popping smaller right-moving asteroids.
The Asteroid Collision problem asks us to simulate the aftermath of a series of asteroid collisions in a single row. We are given an array where the absolute value represents size and the sign represents direction (positive for right, negative for left). When two asteroids collide, the smaller one explodes. If they are the same size, both explode. We need to return the state of the asteroids after all collisions are resolved.
This is a popular interview question, and the optimal LeetCode 735 Solution requires handling sequential dependencies efficiently.
The naive approach attempts to simulate the collisions by repeatedly scanning the array for adjacent collision pairs. A collision pair is defined as a positive number immediately followed by a negative number (e.g., [..., 10, -5, ...]).
i where asteroids[i] > 0 and asteroids[i+1] < 0.Pseudo-Code:
textwhile collision_exists: find index i where asteroids[i] is right(+) and asteroids[i+1] is left(-) if abs(asteroids[i]) > abs(asteroids[i+1]): remove asteroids[i+1] else if abs(asteroids[i]) < abs(asteroids[i+1]): remove asteroids[i] else: remove both
Why this fails:
The time complexity of this approach is O(N²). Removing elements from an array (shifting subsequent elements) takes O(N) time. In the worst-case scenario (e.g., many right-moving asteroids followed by many left-moving asteroids), we might perform O(N) removals. Given the constraint N <= 10^4, an O(N²) solution performs roughly operations, which may lead to a Time Limit Exceeded (TLE) error or perform poorly in an interview setting.
The key intuition is that we can process the asteroids from left to right and maintain a "stable" state of survivors in a stack.
The stack represents the asteroids that have survived all collisions so far and are currently moving safely.
When we encounter a Left-Moving asteroid, we check it against the top of the stack (the rightmost survivor). We repeatedly "pop" from the stack as long as the incoming left-asteroid destroys the stack top. If the stack top destroys the incoming asteroid, we stop.
Visual Description: Imagine the stack as the "safe zone" to the left of our current position.
5 (Right). Stack: [5].10 (Right). Stack: [5, 10].-5 (Left). It clashes with 10. Since 10 > |-5|, the -5 explodes. The stack remains [5, 10].-15 instead: It clashes with 10. 10 explodes (pop). Then it clashes with 5. 5 explodes (pop). The stack becomes empty, and -15 survives (push).![]()
Consider Input: [10, 2, -5]
[]10:
10.[10]2:
2.[10, 2]-5:
2) is Positive. Collision!|-5| vs 2. 5 > 2.2 explodes (Pop).[10]. Current -5 is still alive.10) is Positive. Collision!|-5| vs 10. 5 < 10.-5 explodes.-5.[10][10]The algorithm maintains an invariant: the stack always contains a sequence of asteroids that will never collide with each other. This is guaranteed because:
cppclass Solution { public: vector<int> asteroidCollision(vector<int>& asteroids) { vector<int> st; // Using vector as a stack for easy result return for (int asteroid : asteroids) { bool exploded = false; // Collision loop: while current is moving left (-) and top is moving right (+) while (!st.empty() && asteroid < 0 && st.back() > 0) { if (abs(asteroid) > st.back()) { st.pop_back(); // Top explodes, current continues continue; } else if (abs(asteroid) == st.back()) { st.pop_back(); // Both explode exploded = true; break; } else { exploded = true; // Current explodes break; } } if (!exploded) { st.push_back(asteroid); } } return st; } };
javaclass Solution { public int[] asteroidCollision(int[] asteroids) { Stack<Integer> stack = new Stack<>(); for (int asteroid : asteroids) { boolean exploded = false; // Handle collision while (!stack.isEmpty() && asteroid < 0 && stack.peek() > 0) { if (Math.abs(asteroid) > stack.peek()) { stack.pop(); // Top explodes continue; } else if (Math.abs(asteroid) == stack.peek()) { stack.pop(); // Both explode exploded = true; break; } else { exploded = true; // Current explodes break; } } if (!exploded) { stack.push(asteroid); } } // Convert stack to array int[] result = new int[stack.size()]; for (int i = result.length - 1; i >= 0; i--) { result[i] = stack.pop(); } return result; } }
pythonclass Solution: def asteroidCollision(self, asteroids: List[int]) -> List[int]: stack = [] for asteroid in asteroids: # Flag to track if the current asteroid survives exploded = False # Collision happens if stack has right-moving (+) and current is left-moving (-) while stack and asteroid < 0 and stack[-1] > 0: if abs(asteroid) > stack[-1]: stack.pop() # Top explodes, check next continue elif abs(asteroid) == stack[-1]: stack.pop() # Both explode exploded = True break else: exploded = True # Current explodes break if not exploded: stack.append(asteroid) return stack
Time Complexity: We iterate through the array of asteroids once. Each asteroid is pushed onto the stack at most once and popped at most once. Therefore, the total number of operations is proportional to .
Space Complexity: In the worst case (e.g., all asteroids moving in the same direction), the stack will store all asteroids.
The Stack - Simulation / Backtracking Helper pattern is versatile. It applies when element interactions depend on immediate history.
.. pops the previous directory).Why does the naive solution fail?
Why is my logic failing on [-5, -10]?
Why is the "Both Explode" case tricky?