Problem Statement
Given a permutation p of [1..n], find a sequence to sort the permutation using two stacks, with possibly interleaving push/pop operations or determine it’s impossible.
Constraint: n ~ 2e5
Example: [5 2 4 1 6 3]
Sequence:
push 1 [5] []
push 2 [5] [2]
push 1 [5 4] [2]
push 1 [5 4 1] [2]
pop 1 [5 4] [2]
pop 2 [5 4] []
push 2 [5 4] [6]
...
Hint
According to this paper which references this book, the problem of m-stack sorting in gerneral is equivalent to the m-coloring problem of the graph generated by the rule:
For every index i,j,k which match the pattern 231
(i.e. i < j < k and p[k] < p[i] < p[j]),
there is an egde between p[i] and p[j]
However, recreate the whole graph is infeasible under the constraint; an ‘mountain’ permutation’s graph can have as much as $O(n^2)$ edges. Instead we are going to build the connected components and recolor them on the fly. The key observation is for every index i we need 2 information:
- Of all element on the right, what is the minimum? (This contributes to the 1 in the pattern)
- Of all connected components that we build on the left, which ones has an element that is larger than the previous minimum?
Luckily, both of those question can be answered by maintain the priority queue for each component.
The second challenging part is (re)coloring: If any component has both black and white vertices that satisfy the second condition above, then we cannot 2-coloring the graph. Otherwise, we can merge it with the current component, and recolor if needed. The final trick under the sleeve is small-to-large merging to achieve the $O(n \log n)$ runtime.
Impl
DIY