Assume we have i stacks. the possible actions are:
- push to first stack form input
- pop from stack i and push it to stack i+1
- pop from last stack to output
If we have numbers of 1 to n starting from 1 in the input, what is the minimum value of i which can generate all permutations of 1 to n at the output?
The options are:
Option 1 obviously is not the answer, and also it’s totally possible with n and n-1 stacks witch removes the option 4.
The real question is “is it possible doing it with 2 stacks or we need n-1” ?