how to test a pop order is legal or not?

Question

Given two unique number sequences: push order of stack and pop order of stack, numbers in push order are in ascending sort order, now ask the pop order is legal or not ?

For example, the push order is 1 2 3 4 5, so 4 5 3 2 1 is a legal pop order, because we can push and pop like this:

push 1, push 2, push 3, push 4, pop, push 5, pop, pop, pop, pop

so pop order: 4 5 3 2 1 is legal, and 4 3 5 1 2 is not a legal pop order.

Answer 1

Since your push sequence is in ascending order, then when you see a number N in your pop queue, then all numbers that is 1) below N and 2) not yet popped, must be popped in descending order.

For example, 4 3 5 1 2 is not a valid order, since when we see '4' popped, than all numbers smaller than '4' but not yet popped before must be popped in descending order. However, popping '1' first and then '2' violates this property.

Answer 2

Assumption: The push order and the pop order contains exactly the same numbers. If this is not a valid assumption, it can be validated using a hash-set (or hash-map with counts if there can be duplicates) in linear time, although this would compromise the O(1) space complexity.

Idea: Every element in the pop order must either be less than the element before it, or more than the maximum so far, otherwise the pop order is not valid.

This can be checked in O(n) time and O(1) space by just keeping track of the maximum.

Why this works:

The push order is in ascending order, thus, regardless of when you pop elements:

1. The stack will always be ascending order as well and
2. The next item in the push order will always be larger than the largest element seen on the stack.

So there are two options:

• Two pop operations in a row - in this case the second element will be smaller
• Two pop operations with one or more push operations in between - in this case the second element will be larger than the maximum (following from 2.)

Examples:

4 5 3 2 1 is valid since 5 > max (4), 3 < 5, 2 < 3 and 1 < 2.

4 3 5 1 2 is not valid since 2 > 1 but 2 < max (5).

1 2 3 5 4 is valid since 2 > max (1), 3 > max (2), 5 > max (3) and 4 < 5.