@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<int> SortedStack(Stack<int> s){
stack<int> 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 <prateek10011...@gmail.com>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 <avi.du...@gmail.com> wrote:
>
>> Code is here <http://codebin.org/view/30e9f2c0>. 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 <macatad...@gmail.com> 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.
