167. Was This Pop Order Possible?
Challenge1000 ms256 MBSolved by 0%
Values 1 to n are pushed onto a stack in that order, but a pop may happen
at any point between pushes.
Read n and a proposed pop order, and print Yes if some sequence of pushes and pops
could produce it, or No if it is impossible.
With n = 3, the order 3 2 1 is possible, push all three, then pop all three. The order
3 1 2 is not.
Constraints - `1 ≤ n ≤ 200000` - The pop order is a permutation of 1 to n.
Input
The first line contains an integer n.
The second line contains a permutation of 1 to n, the proposed pop order.
Output
Print exactly one word: Yes or No.
Input3
3 2 1
OutputYes
Notepushes everything then pops everything
Input3
3 1 2
OutputNo
Noteis impossible, because 2 is buried under nothing once 3 leaves
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.