The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 votes

Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence $\text{1, 2, 3, 4, 5}$ in that order?

  1. $\text{3, 4, 5, 1, 2}$
  2. $\text{3, 4, 5, 2, 1}$
  3. $\text{1, 5, 2, 3, 4}$
  4. $\text{5, 4, 3, 1, 2}$
asked in DS by Veteran (52k points)
edited by | 5.2k views

4 Answers

+27 votes
Best answer

Push $1$ push $2$ push $3$ pop $3$ push $4$ pop $4$ push $5$ pop $5$ pop $2$ pop $1$ then o/p is $3,4,5,2,1$

So, option is B.

answered by Boss (11.1k points)
edited by
Why not d)
D is not possible Cz

To pop 5 first...we have to push1,2,3,4,5 then pop 5,4,3

Now we can't remove 1 directly bcz 2 is in Top of stack. So option D is not possible.
As I understood

We r putting the element in order 1,2,3,4,5

In the stack

And we are popping in the sequence 5,4,3,2,1

And  I found it is possible with a ,b , d option .
see my answer . hope it helps :)
can any one tell me why did we used only 3 boxes in the stack to implement this particular problem?
you can see any  stack size, that is not an issue here. these questions the easier method is just try out each option and see whether it is valid. for example take option A.

3, 4, 5, 1, 2

it is given in question push is in order 1 2 3 4 5.

in the op 3 is coming first. so it means 1 2 3 are pushed (3 elements in stack)

now pop 3. stack becomes 1 2

then next o/p is 4 . we need to push 4, then only it  can be popped

now stack 1 2 4

now pop 4

next is 5 similar manner push and pop 5

now stack becomes 1 2 and 2 being on top

in the option next is 1. so it is not possible, because next pop can give only 2

in every step it have max 3 elements in the stack. there is nothing magical in the number 3 used here. you can do the same operations with stack of other size. if you have confusion just draw with               stack size 5. no problems
+12 votes
How to do this within second @ GATE.

Conclusion after long analysis...

Algo..(if values are in increasing order then no problem..but when decrease.. Plz see the range of values between consecutive increased and decrease no. and verify that range of values must appear in ur current state of  input sequence if not then it is invalid sequence.)


3,4,5(increase order no problem)


Now check range of values between 1 to 5( I.e.2,3,4) but 2 not came till now...So invalid sequence.

C. 1,5(Increase order no problem),2(decreased)

See range between 2-5 (means 3,4) which are not came in sequence till now so invalid sequence.

D.5,4(decreased) but there is no value in-between of (4-5)

Now 3 came(decreased) but no Value between 3-4 so ok

Now 1 came ...between 1-3 there is 2 but Still 2 not came in sequence so invalid.

B. 3,4,5,(increased order),2(decreased)

Between 2-5 (3,4)which Already came in sequence so no problem.

Now 1(decreased) .between 1-2 no value is there.. So this is correct sequence.

So option B is Ans.

Once U practice this U can identify Correct sequence within seconds.

PS:--Concepts make shortcut... Not vice versa.. So practice with concept too
answered by Boss (23.4k points)

Rajesh Pradhan

very nice... :) 

+6 votes

hope this helps :)

answered by Active (3.3k points)
great explanation
+3 votes

1,2,3,4,5 in this given sequence 1 is pushed in as 1st element or in other word we can say 1 is the last element of the stack which was popped out in output so check in given options which option have last pop as 1 option (B) 3,4,5,2,1 have last element so option B is answer 

answered by Boss (10.5k points)
Very Nice..give me some more tricks like this

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,541 questions
54,094 answers
71,002 users