# What's Left Standing > They only meet head-on, and only mass decides who keeps going. Canonical URL: Domain: Python · Difficulty: medium · Seniority: L5 ## Problem A one-dimensional physics sim hands you a row of moving particles as nonzero integers, where the sign is the direction (positive drifts right, negative drifts left) and the magnitude is the mass. Particles collide only when a right-mover is caught up to a left-mover ahead of it; the heavier one survives the impact and keeps going, while same-direction or diverging particles pass untouched. Return `particles` after every collision has played out, in its original order. ## Worked solution and explanation ### What this problem really is Strip the sci-fi costume and this is a cascading pairwise-reduction problem: as you sweep left to right, each left-moving particle has to fight not just its neighbor but every right-moving survivor still standing behind it, most recent first. That last-in-first-out challenge order is the entire problem. Anyone can compare two adjacent particles. The separator is realizing that destroying one survivor can re-expose an earlier one that now has to fight the same incoming particle, which is exactly what a growable stack of survivors gives you. Miss it and [10, 2, -5] keeps the 2 or drops the 10: a heavy left-mover that should plow through several right-movers stops at the first. --- ### Break down the requirements #### Step 1: Read the sign, not the number The sign is the direction and the magnitude is the mass. A collision is possible only when a right-moving particle (positive) is immediately to the left of a left-moving particle (negative), so they close on each other. Two particles moving the same way, or a left-mover already ahead of a right-mover, drift apart and never meet. #### Step 2: Keep a stack of survivors Sweep the row left to right and keep a stack of the particles that have survived so far. A right-mover always gets pushed: nothing behind it can catch it. The interesting case is an incoming left-mover, because it is the only thing that can collide with what is already on the stack. #### Step 3: Resolve the cascade with an inner loop When a left-mover arrives, run an inner loop while it is still alive and the top of the stack is a right-mover. Compare masses: if the top is lighter, pop it and let the left-mover keep fighting the next survivor; if they are equal, pop the top and the left-mover also dies; if the top is heavier, the left-mover dies. If it survives the whole gauntlet (the stack empties of right-movers, or the top is another left-mover), push it. --- ### The solution **Single-pass stack reduction** ```python def resolve_collisions(particles): survivors = [] for particle in particles: alive = True while alive and particle < 0 and survivors and survivors[-1] > 0: top = survivors[-1] if top < -particle: survivors.pop() # lighter right-mover explodes, keep fighting elif top == -particle: survivors.pop() # equal mass, both explode alive = False else: alive = False # heavier right-mover survives, incoming dies if alive: survivors.append(particle) return survivors ``` > **Cost analysis** > > The whole thing is O(n) time. Each particle is pushed onto the stack at most once and popped at most once, so across the entire sweep the inner loop does at most n pops total, even though a single left-mover can trigger several pops in a row. The nested loop looks quadratic and is not: the pops are amortized against pushes. Space is O(n) for the survivor stack in the worst case, when nothing collides. > **Interviewers watch for** > > Whether you gate the collision on direction (only a right-mover on top can be hit by an incoming left-mover), whether the inner loop keeps fighting after a pop instead of stopping, and whether equal masses annihilate both. Strong candidates also say out loud why the nested loop is still linear: each element is pushed and popped at most once. The tell for a weaker answer is a single comparison per particle that silently drops the cascade. > **Common pitfall** > > The classic miss is comparing each particle only against its immediate neighbor and never re-checking the survivors behind the one just destroyed. The visible case [10, 2, -5] catches it: the -5 must destroy the 2 and then still lose to the 10, so the answer is [10], not [10, 2]. The other miss is forgetting that equal masses both explode, which [8, -8] pins down: the result is empty, not [8] or [-8]. **Adjacent-only pass** Walk the list once and compare each particle to the one before it. Works on [5, 10, -5] by luck, but on [10, 2, -5] it destroys the 2 and stops, keeping [10, 2]. A heavy left-mover never reaches the survivors hiding behind the first thing it kills. **Stack of survivors** Push survivors; when a left-mover arrives, pop lighter right-movers off the top one by one until it dies, ties, or the top is no longer a right-mover. Re-exposing an earlier survivor is automatic, because it is simply the new top of the stack. --- ## Common follow-up questions - What single line changes if, on equal mass, you want the right-mover to survive instead of both exploding? _(Tests whether the candidate can localize a rule change to one branch. The tie case is the elif that pops and kills the incoming particle; surviving the right-mover instead means popping the top but keeping the incoming one alive.)_ - The inner loop is nested inside the outer loop. Convince me the total work is still O(n). _(Tests understanding that the linear bound is a whole-sequence claim, not a per-call one. A single incoming left-mover can trigger up to n pops, but that cost is repaid because those survivors were each pushed exactly once.)_ - Where else does this push-then-cancel-recent-survivors pattern show up in real systems? _(Tests recognition of the single-pass stack-reduction pattern beyond this puzzle: matching brackets, evaluating expressions, removing adjacent duplicates, and any streaming reduction where a new element cancels recent ones.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/what_s_left_standing) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.