Hi Guys
A more space efficient solution is here
push(x)
{
if stack.empty()
{
stack.push(x);
stack.push(x);
}
else
{
if x > stack.top()
{
min = stack.pop()
stack.push(x)
stack.push(min)
}
else
{
stack.push(x)
stack.push(x)
}
}
}
pop()
{
cmin = stack.pop()
rval = stack.pop()
if (rval != cmin)
stack.push(cmin)
return rval
}
min()
{
return stack.top()
}
It consumes 2n space in the worst case (same as existing solution) and with
same time complexity.
Here is how it works for the input 6,5,10,3,9,1
(6,6)
(6,6)(5,5)
(6,6)(5,10,5)
(6,6)(5,10,5)(3,3)
(6,6)(5,10,5)(3,9,3)
(6,6)(5,10,5)(3,9,3)(1,1)
On Thu, Oct 8, 2009 at 9:33 PM, Satyam Shekhar <satyamshek...@gmail.com>wrote:
>
> Dave, we don't remove (3,3)...
> min_query will return 3 stored at the top..ie (9,3)..
> pop will remove (9,3).. not (3,3)
>
> On Thu, Oct 8, 2009 at 8:47 PM, sharad kumar <aryansmit3...@gmail.com>
> wrote:
> > 3 is min element then y to return 5??if u remove 9,3
> > 3 at tos 3 is min so y to remove 5 borther dave
> >
> > On Thu, Oct 8, 2009 at 8:37 PM, Dave <dave_and_da...@juno.com> wrote:
> >>
> >> Satyam, let's work your example in detail. We've pushed your data onto
> >> the stack, and now we start popping.
> >>
> >> (6,6),(5,5),(10,5),(3,3),(9,3),(1,1), so remove the (1,1) and return
> >> 1.
> >> (6,6),(5,5),(10,5),(3,3),(9,3) so remove (3,3) and return 3.
> >> (6,6),(5,5),(10,5),(9,3). Now what? How do we find (5,5) to return 5?
> >>
> >> Dave
> >>
> >>
> >> On Oct 8, 6:15 am, harit agarwal <agarwalha...@gmail.com> wrote:
> >> > @manisha
> >> > i think u didn't get my point
> >> >
> >> > every time it will return the different value
> >> > ex
> >> > values to be pushed 6,5,10,3,9,1
> >> > now push(a,b) a=element b=minimum value pushed till now
> >> > (6,6)
> >> > (6,6),(5,5)
> >> > (6,6),(5,5),(10,5)
> >> > (6,6),(5,5),(10,5),(3,3)
> >> > (6,6),(5,5),(10,5),(3,3),(9,3)
> >> > (6,6),(5,5),(10,5),(3,3),(9,3),(1,1)
> >> >
> >> > now start popping
> >> > (1,1) min in stack=1
> >> > (9,3) min in stack =3
> >> > similarly
> >> > last (6,6) min in stack=6
> >> >
> >> > so everytime u get min in O(1)
> >>
> >
> >
> > >
> >
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
