Stacks and Monotonic Structures
Processing in the right order, then absorbing
Sort so that the collapse becomes local, then let a stack do the collapsing.
Key idea
When items swallow each other
Some problems describe items that interact and merge: things collide, catch up, or block one another. The answer is how many survive, or what the survivors look like.
These are stack problems because an interaction is always between the newest item and the most recent survivor, and resolving it may expose an older survivor to the same test. That cascade is exactly what a stack handles in one pass.
Here is the pattern on collisions. Values move right when positive and left when negative. Two that meet destroy the smaller in magnitude, or both if equal.
Why it works
The cascade is the point
In the third example the incoming -5 destroys the 2, and then has to be tested against the 10 that was underneath. One incoming item can consume several survivors, and only a structure that exposes the next survivor after each removal makes that natural.
The condition on the while is worth reading carefully: an interaction only happens when the top is moving right and the incoming is moving left. Every other combination means they never meet, and the incoming item simply joins the survivors.
Key idea
Sorting to make the interaction local
The example above arrives in the order that matters. Frequently it does not, and the first move is to sort into an order where interactions only ever happen between neighbors.
That is a real design decision. Ask what has to be true for item A to affect item B, then sort by whatever makes that relationship point in one consistent direction. Once neighbors are the only thing that can interact, a stack finishes the job.
Tip
Sorting by position, comparing by time
A useful special case: things moving along a line toward a common destination. Sorting by position tells you who is ahead. What decides whether one catches another is not position but arrival time, computed from the remaining distance and the speed.
So you sort by one quantity and compare by another. Something that would arrive sooner than the thing ahead of it never actually arrives sooner, because it gets stuck behind. That is an absorption, and the group takes the slower time.
Working out which quantity to sort by and which to compare is the entire problem below. Do it on paper with three items before writing any code.
Gotcha
Scanning from the wrong end
For catch-up problems the natural scan is from the destination backward, because whether something is blocked depends only on what is ahead of it, and what is ahead has already been resolved.
Scanning the other way forces you to revisit decisions when a later item turns out to block an earlier one. If a stack solution feels like it needs to look ahead, try reversing the scan before adding complexity.
Which way should the scan run?
Cars travel along a road toward a shared finish line at different speeds and cannot pass each other. You want to count how many distinct groups arrive. In which order should the cars be processed?
Car Fleet
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.