Colliding Particles
MediumStack
Problem
Particles sit on a line in the order given by particles. Each value is non-zero: its absolute value is the particle's mass and its sign is its direction (positive moves right, negative moves left). All particles move at the same speed.
When a right-mover meets a left-mover, the lighter one is destroyed; if their masses are equal, both are destroyed. Particles moving in the same direction never meet. Return the particles that survive, in their original order.
Example 1
- Input:
- particles = [6, 3, -4]
- Output:
- [6]
-4 destroys 3, then meets 6 and is destroyed.
Example 2
- Input:
- particles = [-2, -1, 1, 2]
- Output:
- [-2, -1, 1, 2]
The left-movers are already on the left and move away; nothing meets.
Example 3
- Input:
- particles = [7, -7]
- Output:
- []
Constraints
- 2 ≤ particles.length ≤ 10^4
- -1000 ≤ particles[i] ≤ 1000
- particles[i] ≠ 0
Hint
Show the first hint
Only a left-mover arriving after right-movers can cause a collision. Which right-mover does it hit first?
Walkthrough
How to approach it
01Clarify before coding
- Do a left-mover on the left and a right-mover on the right ever meet? No, they move apart.
- What if masses tie? Both disappear.
- Should the output keep the original order? Yes.
02Brute force
Simulate rounds: in each round find any adjacent pair (right-mover, left-mover), resolve it, and repeat until no such pair exists.
Cost: Up to n collisions, each found by an O(n) scan: O(n²).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.