939 views
2 votes
2 votes

The question basically says no. of different outputs produced for given sequence of input (1,2,...,n)

I thought in terms of push - pop pairs but cant arrive at the answer 

@arjun sir , @bikram sir

1 Answer

Best answer
4 votes
4 votes

I thought in terms of push - pop pairs but cant arrive at the answer 

You are very very close to the answer. Let us first see what we get when $n=3$ and later generalize it.

So for an input sequence, $1,2,3$ following are the possible permutations we can get as output as a result of the pop operations in some order.

$$<1,2,3>, <1,3,2>, <3,2,1>, <2,1,3>, <2,3,1>$$

Note that $<3,1,2>$ is not possible as we have to wait until $3$ is pushed into the stack and then pop it to get it first in the permutation. But at this point, we cannot pop $1$ before $2$.

That gives us $5$ out of $6$ possible permutation of the input sequence. Plug $n=3$ in all the options and you see only option (B) gives us $5$.


To obtain certain sequence as output we perform push and pop operation in some order. For every push operation, write down a left parenthesis and for every pop operation, write a corresponding right parenthesis.

For instance, to obtain the sequence $<1,3,2>$ in the above example we do following push pop operation

$$<push(1), pop(1), push(2), push(3), pop(3), pop(2)>$$

After parenthesization substitution we get this $()(())$

Thus for all possible valid permutations possible as an output of push and pop operation in some order is actually all possible enumeration of proper parenthesization which is given by Catalan Number

HTH

selected by

Related questions

0 votes
0 votes
1 answer
1
Abhrajyoti00 asked Oct 29, 2022
718 views
Can there be “Stack Overflow” in Linked list Implementation of stack? If Yes, how?
1 votes
1 votes
0 answers
2
srestha asked Apr 3, 2019
1,539 views
Is it TRUE or FALSE?Stack allocation can allocate and deallocate dynamic variables and can manage runtime storage
2 votes
2 votes
2 answers
3
1 votes
1 votes
2 answers
4
Shamim Ahmed asked Dec 11, 2018
689 views
Every recursive program uses strictly more stack space compared to its iterative equivalent.This statement is false. Please explain with examples