← Create New Paste

Asteroid Collision (LeetCode 735): A Stack Simulation Interview Problem

6 views
You get an array of integers representing asteroids in a row. The absolute value is the size; the sign is the direction (positive moves right, negative moves left). All move at the same speed. When two meet, the smaller one explodes; if they are equal, both explode. Return the state after all collisions. Example: [5, 10, -5] becomes [5, 10], and [10, 2, -5] becomes [10]. Why interviewers like it The problem is short, but it tests whether you can model a process precisely. Most bugs come from collision rules, not from the data structure. Key observation Only one pattern collides: a right-moving asteroid on the left meeting a left-moving asteroid on the right. Two asteroids moving apart never meet, and a left-mover that arrives first simply keeps going. So scan left to right and keep the survivors on a stack. def asteroid_collision(asteroids): stack = [] for a in asteroids: alive = True while alive and a < 0 and stack and stack[-1] > 0: top = stack[-1] if top < -a: stack.pop() # top explodes, a keeps going elif top == -a: stack.pop() # both explode alive = False else: alive = False # a explodes if alive: stack.append(a) return stack Each asteroid is pushed and popped at most once, so the run time is O(n) even with the inner while loop, and the extra space is O(n). Edge cases to say out loud - [-2, -1, 1, 2]: nothing collides, because the left-movers are already on the left. - [8, -8]: both disappear; make sure you do not push the negative one afterwards. - [1, -2, -2, -2]: the first negative destroys the 1, and the rest pass freely. - An empty input should return an empty list. Walking through [10, 2, -5]: push 10, push 2. For -5, the top 2 is smaller, so pop it; the next top 10 is bigger, so -5 explodes. Result [10]. Common follow-ups - Return only the number of survivors: same algorithm, return len(stack). - Different speeds: now timing matters, and the problem becomes an event simulation with a priority queue, a good chance to discuss how assumptions drive the design. - Related stack problems: evaluating reverse Polish notation and removing adjacent duplicates use the same "compare with the top, then pop or push" pattern. Interview delivery State the one collision pattern first, write the loop with a clear alive flag, and trace two examples. If you lose the thread on the equal-size case under pressure, Linkjob AI (https://linkjob.ai) offers real-time help during live technical interviews, giving quiet hints so you can keep explaining your reasoning in your own words.
Created Nov 17, 2026 19:56 Expires Nov 17, 2027 19:56