⚡Flashcard Drill➔
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

  1. 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.
  2. So the loop condition is a < 0 and stack and stack[-1] > 0.
  3. Resolve each collision: pop if the stack top is smaller, break if it is larger, and pop both if equal.
  4. Use an alive flag 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] with a directly: a is negative, so the magnitudes must be compared via -a.
  • Allowing collisions between same-direction asteroids: the a < 0 and st[-1] > 0 guard is what restricts collisions to opposing pairs.
  • Forgetting the alive flag: 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.
🎯 Drill This Card Now➔

🧩 Related Stack Problems