we can use another stack to store the min/max number in stead of using pointers in every item. At the time of push, we have to do normal push in the first stack and in the extra stack, we can check the top value, if it's greater than the current item, we should push the current item in the extra stack also. on the similar lines, pop() can be implemented.
On Fri, Oct 1, 2010 at 1:12 AM, Gene <[email protected]> wrote: > > 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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- 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.
