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 <[email protected]>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 <[email protected]>
> 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 <[email protected]> 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 <[email protected]> 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 [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
-~----------~----~----~----~------~----~------~--~---
