Re: [algogeeks] stack. Mid element in o(1)

[Nikhil Agarwal]

@Prateek Jain : Middle element is nothing but a median ( i.e. middle
element in sorted state)

Soluton

1. Maintain a sorted stack using an extra stack , pop half of the elements
or get the middle and if it's implemented using arrays fetch middle index
value (top/2)
T(N)= O(n^2) to maintain a sorted stack.

Code :
stack SortedStack(Stack s){
stack r;
int temp;
while(!s.empty())
{
temp=s.top():
s.pop();
while(!r.empty && r.top()>temp){
s.push(r.top());
r.pop();
}
r.push(temp);
}
return r;
}



On Thu, May 23, 2013 at 2:38 PM, Prateek Jain wrote:

> I think there is no need for such a complex code. use length() method to
> get the size of the stack and return the middle element i.e.
>
> m=S.length()
> if(m is even)
> return arr[m/2]
>
> else
> return arr[m+1/2]
>
> it can be done in O(const) time
>
>
> On Thu, May 23, 2013 at 12:54 PM, Avi Dullu  wrote:
>
>> Code is here . Logic is made clear by
>> the variable names. Idea is similar to the one which is used to build a
>> queue using 2 stacks.
>>
>>
>> On Wed, May 22, 2013 at 8:45 AM, MAC  wrote:
>>
>>> I think this is only possible if you make sure that at push you store
>>> the middle element with the top element as well .. this would mean push
>>> would cease to be o(1)   & become o(n) .. . or is there some other trick ?
>>>
>>
>>
>>
>> Veni Vedi Slumber !
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>>
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
>
>



-- 
Thanks & Regards
Nikhil Agarwal
B.Tech. in Computer Science & Engineering
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] stack. Mid element in o(1)

[Tian Guo]

Using two stacks to simulate the getmiddle behavior.

Amortized analysis can show each geimiddle is O(1) time complexity.

Best,


2013/5/23 Prateek Jain 

> I think there is no need for such a complex code. use length() method to
> get the size of the stack and return the middle element i.e.
>
> m=S.length()
> if(m is even)
> return arr[m/2]
>
> else
> return arr[m+1/2]
>
> it can be done in O(const) time
>
>
> On Thu, May 23, 2013 at 12:54 PM, Avi Dullu  wrote:
>
>> Code is here . Logic is made clear by
>> the variable names. Idea is similar to the one which is used to build a
>> queue using 2 stacks.
>>
>>
>> On Wed, May 22, 2013 at 8:45 AM, MAC  wrote:
>>
>>> I think this is only possible if you make sure that at push you store
>>> the middle element with the top element as well .. this would mean push
>>> would cease to be o(1)   & become o(n) .. . or is there some other trick ?
>>>
>>
>>
>>
>> Veni Vedi Slumber !
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>>
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] stack. Mid element in o(1)

[Prateek Jain]

I think there is no need for such a complex code. use length() method to
get the size of the stack and return the middle element i.e.

m=S.length()
if(m is even)
return arr[m/2]

else
return arr[m+1/2]

it can be done in O(const) time


On Thu, May 23, 2013 at 12:54 PM, Avi Dullu  wrote:

> Code is here . Logic is made clear by
> the variable names. Idea is similar to the one which is used to build a
> queue using 2 stacks.
>
>
> On Wed, May 22, 2013 at 8:45 AM, MAC  wrote:
>
>> I think this is only possible if you make sure that at push you store the
>> middle element with the top element as well .. this would mean push would
>> cease to be o(1)   & become o(n) .. . or is there some other trick ?
>>
>
>
>
> Veni Vedi Slumber !
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] stack. Mid element in o(1)

[Avi Dullu]

Code is here . Logic is made clear by the
variable names. Idea is similar to the one which is used to build a queue
using 2 stacks.


On Wed, May 22, 2013 at 8:45 AM, MAC  wrote:

> I think this is only possible if you make sure that at push you store the
> middle element with the top element as well .. this would mean push would
> cease to be o(1)   & become o(n) .. . or is there some other trick ?
>



Veni Vedi Slumber !

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] stack. Mid element in o(1)

[MAC]

Saw this on  a seperate group .. Since answer not known to me sharing it
here

you have a stack . Exposed functionality is push and pop only .

What minimal modifications would you do such that
you should find middle element in o(1) time .

I think this is only possible if you make sure that at push you store the
middle element with the top element as well .. this would mean push would
cease to be o(1)   & become o(n) .. . or is there some other trick ?


thanks
--mac

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.