Monday, November 14, 2011

No. 21 - Push and Pop Sequences of Stacks

Problem: Given two integer sequences, one of which is the push sequence of a stack, please check whether the other sequence is a corresponding pop sequence or not.

For example, if 1, 2, 3, 4, 5 is a push sequence, 4, 5, 3, 2, 1 is a corresponding pop sequence, but the sequence 4, 3, 5, 1, 2 is not.

Analysis: An intuitive thought on this problem is to create an auxiliary stack. We push the numbers in the first sequence one by one, and try to pop them out according to the order in the second sequence.

Take the sequence 4, 5, 3, 2, 1 as an example to analyze the process to push and pop. The first number to be popped is 4, so we need to push it into a stack. The pushing order is defined in the first sequence, where there are numbers 1, 2 and 3 prior to 4. Therefore, numbers 1, 2, and 3 are pushed into a stack before 4 is pushed. At this time, there are 4 numbers in a stack, which are 1, 2, 3 and 4, with 4 on top. When 4 is popped, numbers 1, 2 and 3 are left. The next number to be popped is 5, which is not on top of stack, so we have to push numbers in the first sequence into stack until 5 is pushed. When number 5 is on top of a stack, we can pop it. The next three numbers to be popped are 3, 2 and 1. Since these numbers are on top of a stack before pop operations, they can be popped directly. The whole process to push and pop is summarized in Table 1.

 Step Operation Stack Status Popped Step Operation Stack Status Popped 1 Push 1 1 6 Push 5 1, 2, 3, 5 2 Push 2 1, 2 7 Pop 1, 2, 3 5 3 Push 3 1, 2, 3 8 Pop 1, 2 3 4 Push 4 1, 2, 3, 4 9 Pop 1 2 5 Pop 1, 2, 3 4 10 Pop 1
Table 1: The process to push and pop with a push sequence 1, 2, 3, 4, 5 and pop sequence 4, 5, 3, 2, 1

Let us continue to analyze another pop sequence 4, 3, 5, 1, 2. The process to pop the first number 4 is similar to the process above. After the number 4 is popped, 3 is on the top of stack and it can be popped. The next number to be popped is 5. Since it is not on top, we have to push numbers in the first sequence until the number 5 is pushed. The number 5 can be popped when it is pushed onto the top of a stack. After 5 is popped out, there are only two numbers 1 and 2 left in stack. The next number to be popped is 1, but it is not on the top of stack. We have to push numbers in the first sequence until 1 is pushed. However, all numbers in the first sequence have been pushed. Therefore, the sequence 4, 3, 5, 1, 2 is not a pop sequence of the stack with push sequence 1, 2, 3, 4, 5. The whole process to push and pop is summarized in Table 2.

 Step Operation Stack Status Popped Step Operation Stack Status Popped 1 Push 1 1 6 Pop 1, 2 3 2 Push 2 1, 2 7 Push 5 1, 2, 5 3 Push 3 1, 2, 3 8 Pop 1, 2 5 4 Push 4 1, 2, 3, 4 The next number to be popped is 1, which is neither on the top of stack, nor in the remaining numbers of push sequence. 5 Pop 1, 2, 3 4
Table 1: The process to push and pop with a push sequence 1, 2, 3, 4, 5 and pop sequence 4, 3, 5, 1, 2

According to the analysis above, we get a solution to check whether a sequence is a pop sequence of a stack or not. If the number to be popped is currently on top of stack, just pop it. If it is not on the top of stack, we have to push remaining numbers into the auxiliary stack until we meet the number to be popped. If the next number to be popped is not remaining in the push sequence, it is not a pop sequence of a stack. The following is some sample code based on this solution:

bool IsPopOrder(const int* pPush, const int* pPop, int nLength)
{
bool bPossible = false;

if(pPush != NULL && pPop != NULL && nLength > 0)
{
const int* pNextPush = pPush;
const int* pNextPop = pPop;

std::stack<int> stackData;

while(pNextPop - pPop < nLength)
{
// When the number to be popped is not on top of stack,
// push some numbers in the push sequence into stack
while(stackData.empty() || stackData.top() != *pNextPop)
{
// If all numbers have been pushed, break
if(pNextPush - pPush == nLength)
break;

stackData.push(*pNextPush);

pNextPush ++;
}

if(stackData.top() != *pNextPop)
break;

stackData.pop();
pNextPop ++;
}

if(stackData.empty() && pNextPop - pPop == nLength)
bPossible = true;
}

return bPossible;
}

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.

1. another method using divid and conquer with constant space and worst case O(nlogn) time (I guess O(n) expected time but I didn't prove it):
push: 1, 2, 3, 4, 5
pop: 4, 5, 3, 2, 1
without loss of generality, let push seq is sorted, do a binary search of first element of pop from push sequence, in this case search for 4, then we have two subproblems which are:

push: 123
pop: 321

and

push: 5
pop:5

2. Your solution does not work on push={1,4,3,4,5} and pop={4,5,3,4,1};
Prove: http://ideone.com/SQtdV

1. This comment has been removed by the author.

3. This algorithm wont give good results if sequence has duplicate numbers.

4. works only in case of unique numbers

5. Hi here's my solution
The concept comes from that the inorder pop sequence means we need to start from some interior point of push array and then sequentially move right(push new number) or left(pop current stack) and clean the push array until we reach the two end of the push array. So, just reverse the procedure and start from the tail of pop sequence, we could have the following code, which could handle duplicate numbers

bool IsPopOrder(const int* pPush, const int* pPop, int nLength)
{
int s = 0;
int e = nLength-1;
for(int i=nLength-1;i>=0;i--)
{
if(pPop[i]==pPush[e])
e--;
else if(pPop[i]==pPush[s])
s++;
else
return false;
}
return true;
}

6. The solution doesn't work when sequence has duplicated values

7. can you extend this for duplicate elements?

8. Hi Mate,

11/10!! Your blog is such a complete read. I like your approach with No. 21 - Push and Pop Sequences of Stacks . Clearly, you wrote it to make learning a cake walk for me.

We're currently in an infinite loop between sales and support, neither of whom seem to be able to understand a basic issue.

We want to purchase some sizeable reserved instances but are told that the only way to pay is all at once with a credit card. No split payments, no offer to pay by check, no offer to pay by ACH, no offer to pay by wire. AWS Training USA

Can someone explain to me how AWS serves enterprises if they only accept consumer methods of payment?

Super likes !!! for this amazing post. I thinks everyone should bookmark this.

Kind Regards,
Ajeeth

9. Salemetsiz Be,

Grazie! Grazie! Grazie! Your blog is indeed quite interesting around No. 21 - Push and Pop Sequences of Stacks I agree with you on lot of points!

Since yesterday my EC2 instance in Singapore has become inaccessible to some US customers. Does anyone else have similar problems? AWS Tutorial

Please keep providing such valuable information.

Cheers,
Ajeeth

10. Marhaba,

Great piece on No. 21 - Push and Pop Sequences of Stacks , I’m a fan of the ‘flowery’ style Looking forward to more long form articles ??

Pretty much 'overnight' we are unable to access couple of our AWS EC2 instances using ssh and/or ftps/scp/sftp methods -> "Connection timed out". At the same time we a r e able to access instances having the same security group (SG) attached, deployed from the same image, configured much the same way, using the same connection methods. Have triple-checked routing, in-host firewall, SG rules, local outgoing policies, etc. AWS Training

Thank you very much and will look for more postings from you.

11. Hey Brother,

Jeez oh man,while I applaud for your writing , it’s just so damn straight to the point No. 21 - Push and Pop Sequences of Stacks .

As far as I can tell from the dashboard, the bill has been paid and we are current again,
AWS Training USA although we are on-track to go over our EBS - Volumes allotment during this billing cycle. How long until our AWS access is restored? Is there anything we can do to expedite the process? Do we need to pay for more EBS- Volumes service?

But nice Article Mate! Great Information! Keep up the good work!