You can use an auxiliary stack to store the minimum values.Lets call
it minstack.
Whenever you push an "Element" in the Original stack, compare it with
the top of minstack.
if it is lesser than top of minstack then push this one on both the
stacks and if not then
push the top of minstack again on itself and push the "Element" onto
the original stack.
While popping elements ,pop both of the stacks and get the element
popped from original stack.
To find minimum just get the top element of the minstack.
Psuedo-code:
elem pop() {
minstack.pop();
return stack.pop();
}
void push(elem x) {
stack.push(x);
if(minstack.top() > x)
minstack.push(x);
else minstack.push(minstack.top());
}
elem findmin(){
return minstack.pop();
}
On Jun 24, 3:33 pm, Piyush Sinha <ecstasy.piy...@gmail.com> wrote:
> ohh sorry, my bad......I missed that issue...then we can use the same logic
> of using one more stack that we use for implementing modified stack keeping
> track of the min()..I hope this will solve the issue
>
>
>
> On Fri, Jun 24, 2011 at 3:57 PM, ross <jagadish1...@gmail.com> wrote:
> > @piyush,
> > Dude, how will that make findmin() to be O(1) because, once the
> > minimum element is
> > deleted, u would require changes in the others .. Correct me if i am
> > wrong..
> > Eg:
> > consider inserting, 1 5 6 7 9 in order into the circular LL.
> > When u make each node keep track of the minm before it, all will
> > retain 1 as minm..
>
> > Now consider deleting 1. how will that affect the rest of the list?
>
> > On Jun 24, 3:07 pm, Piyush Sinha <ecstasy.piy...@gmail.com> wrote:
> > > Can we use circular linked list with each new inserted node keeping track
> > of
> > > the minimum before it??
>
> > > On Fri, Jun 24, 2011 at 3:20 PM, ross <jagadish1...@gmail.com> wrote:
> > > > Hi,
> > > > I know that a stack can be modified with another stack to support push
> > > > pop min in const time.
> > > > Design a FIFO data structure to support ins, del, and find min in
> > > > O(1). Extra space allowed.
>
> > > > --
> > > > You received this message because you are subscribed to the Google
> > Groups
> > > > "Algorithm Geeks" group.
> > > > To post to this group, send email to algogeeks@googlegroups.com.
> > > > To unsubscribe from this group, send email to
> > > > algogeeks+unsubscr...@googlegroups.com.
> > > > For more options, visit this group at
> > > >http://groups.google.com/group/algogeeks?hl=en.
>
> > > --
> > > *Piyush Sinha*
> > > *IIIT, Allahabad*
> > > *+91-8792136657*
> > > *+91-7483122727*
> > > *https://www.facebook.com/profile.php?id=100000655377926*
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> *Piyush Sinha*
> *IIIT, Allahabad*
> *+91-8792136657*
> *+91-7483122727*
> *https://www.facebook.com/profile.php?id=100000655377926*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
