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
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution