850. Can One Stack Sort It
A permutation of 1 .. n arrives in the given order. You have one stack and an output list, and
may perform two moves in any order:
* PUSH the next arriving value onto the stack * POP the top of the stack onto the end of the output
Every value must eventually reach the output. Decide whether the output can be made to read
1, 2, 3, ..., n. Print Yes or No.
2 1 3 4 -> Yes
2 4 1 3 -> No
3 2 1 -> Yes
For 2 1 3 4: push 2, push 1, pop 1, pop 2, push 3, pop 3, push 4, pop 4.
## Why the greedy plan is the only plan
The next value the output needs is fixed, call it want. At any moment there is nothing to
choose: if the top of the stack equals want, popping it is forced, because want will never
become easier to reach by burying it deeper. If it does not, nothing can be popped, so the only
legal move is to push the next arrival.
So the procedure is
want = 1
for each arriving value v:
push v
while the stack is non-empty and the top equals want:
pop, and want = want + 1
answer Yes exactly when the stack is empty at the end
## What the failure actually looks like
The stack is sorted at all times, decreasing from the bottom up: whenever a value larger than the top is pushed it would block the top forever, and it is exactly that situation that fails.
Failure has a name and a shape. The permutation is unsortable precisely when it contains three
positions i < j < k with
a[k] < a[i] < a[j]
that is, a 2-3-1 pattern. The middle value a[i] is pushed first, the large a[j] lands on top
of it, and the small a[k] must be output before either. It cannot be: a[i] is buried under a
value that must come out later, so the order is impossible.
The greedy simulation is what detects this in O(n). The pattern is what explains it, and it is
the mirror image of problem 844.
## Why leftovers mean No
If the stack is non-empty when the input runs out, its top is not want and nothing else can
arrive, so the sequence is stuck. That single test is the whole answer, which is why no separate
failure check is needed inside the loop.
## Related problems
Problem 167 is given BOTH the push order and a proposed pop order and asks whether that pair is consistent. This one is given only the arrival order and asks whether some pop order sorts it. Problem 844 looks for the 1-3-2 pattern; the forbidden shape here is 2-3-1.
## Cost
Time O(n): one push and at most one pop per value. Space O(n).
Constraints - `1 ≤ n ≤ 200000` - the values are a permutation of `1 .. n`
Input
The first line contains one integer n.
The second line contains n integers, a permutation of 1 .. n, in arrival order.
Output
Print one line containing the single word Yes if the output can be made to read 1, 2, 3 and so on, or No if it cannot. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.