NeetCode #354LC-735MediumStackNC 250
← Back to All Problems#354 · #735 · Asteroid Collision(小行星碰撞)
📌 Problem Statement & Constraints
We are given an array
asteroids of integers representing asteroids in a row. The absolute value is the size and the sign is the direction (positive = right, negative = left). When two asteroids collide, the smaller explodes; equal sizes both explode. Asteroids moving in the same direction never collide. Return the state after all collisions. Constraints: 2 <= asteroids.length <= 10^4, -1000 <= asteroids[i] <= 1000, no zero values.💡 Core Algorithmic Approaches
- A stack holds the surviving asteroids. A collision can only happen between a right-moving asteroid on the stack and a left-moving asteroid arriving.
- So the loop condition is
a < 0 and stack and stack[-1] > 0. - Resolve each collision: pop if the stack top is smaller, break if it is larger, and pop both if equal.
- Use an
aliveflag so the incoming asteroid is only pushed if it survives every collision.
💻 Benchmark Python3 Implementation
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
st = []
for a in asteroids:
alive = True
# only a left-mover can collide with a right-mover on the stack
while alive and a < 0 and st and st[-1] > 0:
if st[-1] < -a: # stack top explodes
st.pop()
elif st[-1] == -a: # both explode
st.pop()
alive = False
else: # incoming explodes
alive = False
if alive:
st.append(a)
return st⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each asteroid is pushed once and popped at most once.
💾 Space Complexity
O(n) for the stack.
⚠️ Interview Pitfalls & Follow-ups
- Comparing
st[-1]withadirectly:ais negative, so the magnitudes must be compared via-a. - Allowing collisions between same-direction asteroids: the
a < 0 and st[-1] > 0guard is what restricts collisions to opposing pairs. - Forgetting the
aliveflag: an asteroid that explodes must not be pushed. - Popping both on an unequal collision: only the smaller one explodes.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.