Skip to interview prep
Apexed

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).

If 1..n are pushed in order and pops may be interleaved anywhere, how many output orders are possible — Data structures & algorithms interview question — Apexed