The Gateway to Computer Science Excellence
0 votes
Consider a single array $A\left [ 0...........(n-1) \right ]$ is used to implement two stacks. Two stacks grows from opposite end of the array. Variable  $top_{1}$ and $top_{2}$ points to the location of the topmost elements in each of the stacks with initial values of $-1$ and $n$ respectively and $top_{1}<top_{2}$ always. If  certain push and pop operations are performed in either end, then which of the following represents the number of elements are present in the array at any time?


in DS by Veteran (119k points) | 85 views

2 Answers

+2 votes
Best answer

Ans is B

Initially the array must be empty that is, it must contain 0 number of elements. Now we are given that top 1 = -1 and top2= n

when no elements are inserted the 2 pointers remain in their same location, i.e. -1 and n

now putting these values in equation a and we get

a) n-top2+top1

= n-n+(-1)

= -1

b) n+1−top2+top1

 = n+1-n-1


As we all know initially the elements in the array is 0. therefore b is the ans.. :)

by Active (3.6k points)
selected by


array is from $A\left [ 0,....(n-1) \right ]$


Then how r u taking top1=-1 and top2=n??

It is given in the question itself that top1 and top2 are assigned value -1 and n initially when the array is empty..

Once we insert element on both the sides their values will be incremented and decremented to 0 and n-1 respectively, initially they are -1 and n suggesting that they do not point to any location at all..


But , see the question again

It is asking "number of elements are present in the array at any time"

is that mean anytime stack contains $0$ element?

Suppose take a situation

A stack contains $8$ elements

and it is array location $A\left [ 0,....,7 \right ]$

And Stack1 contains

$A\left [ 0 \right ]=x$,$A\left [ 1 \right ]=y$,$A\left [ 2 \right ]=z$

Stack2 contains

$A\left [ 5 \right ]=u$,$A\left [ 6 \right ]=v$, $A\left [ 7 \right ]=w$

Now apply the formula $B)$

According to formula


Now, that is not correct

because, stack contains only 6 elements

Initially stack contains 0 element and i have used my test case for the same.. if i insert 2 elements now one from top1 and another from top2 the value of top1 becomes 0 and value of top2 becomes n-1

now putting these values in b) n+1−top2+top1 we get n+1-(n-1)+1 = 2 i.e. there are 2 elements in the array..

so it is clear that formula b is the right answer for ANY time..


yes, My bad

Got the logic.

In my example

There is top1 is in a[2], and top1 is in a[5]

So, gap between  in this array is 2 elements , i.e. a[3] and a[4].

But when we actually subtracting , we got 5-2=3 element 

To cancel out that extra 1 we  have to subtract it from (n+1) elements

And thus got total elements

Thanks .

–1 vote
Answer is B.
by (21 points)

@sagar2405 explain plz

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
50,737 questions
57,391 answers
105,442 users