push(), pop() method as stack, and also has a getMinElement(). Require that
getMinElement() is constant time but push()/pop() do not have to be constant
time at first. Then for improvement, these three methods are all required to
be constant time
Define node as
struct node{
int data;
int curr_min;
}
void push(int ele){
new node->data= ele;
if( ele < top->curr_min) new_node-> curr_min=ele;
else new_node->curr_min= top->curr_min;
}
Try to simulate it on paper and think now whether push,pop,getMin are O(1)
or not.
On Wed, Jun 29, 2011 at 12:14 PM, ankit sambyal <[email protected]>wrote:
> @juver++ :
> I don't think it will work in O(1) time. Plz post ur algo. I may
> have misunderstood u !!!
>
>
>
> On Tue, Jun 28, 2011 at 11:37 PM, juver++ <[email protected]> wrote:
> > @samby
> > There is no need to use any other data structures but only stack. Each of
> > its nodes is a pair of a data and minimal element below the current node.
> > Then all updates are done in constant time.
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To view this discussion on the web visit
> > https://groups.google.com/d/msg/algogeeks/-/XQDUXzPp31oJ.
> > 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.
> >
>
> --
> 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.
>
>
--
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.
