Saurabh Singh's method is fine. It's even simpler to use a regular
stack of ints, but re-implement push(x) and pop() to do 3 operations
each.
void mm_push(stack s, int x)
{
int min = mm_min(s);
int max = mm_max(s);
push(s, x);
push(s, x < min ? x : min);
push(s, x > max ? x : max);
}
int mm_pop(stack s)
{
pop(s); pop(s); return pop(s);
}
int mm_max(stack s) { return s[s.top]; }
int mm_min(stack s) { return s[s.top - 1]; }
int mm_top(stack s) { return s[s.top - 2]; }
On Sep 29, 12:06 am, Sathaiah Dontula <[email protected]> wrote:
> Provide DS and algo for push, pop and min or max should be in O(1) (
> constant time) with extra memory and without extra memory.
>
> Will it be possible without extra memory ?
>
> Thanks,
> Sathaiah
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
