121. If 1..n are pushed in order and pops may be interleaved anywhere, how many output orders are possible?
MediumStacks
Technical
Show model answer
The count is the nth Catalan number, C(n) = (2n)! / ((n + 1)! n!): 1, 1, 2, 5, 14, 42 for n = 0..5. Each valid run is a sequence of n pushes and n pops in which pops never outnumber pushes in any prefix, which is the classic Catalan (Dyck path) structure.
For n = 3 only `3 1 2` is impossible: once 3 is output, 1 and 2 are on the stack with 2 above 1, so 2 must come out before 1. More generally, a permutation is reachable exactly when it avoids the pattern where a larger value is followed later by a smaller and then a middle value (the 3-1-2 pattern).