When you push into stack2, you have to recompute the min value. So after you
push into stack2, it will be:
(6,6),(3,3),(4,3),(2,2)
On Thu, Jan 6, 2011 at 6:34 PM, sourav <souravs...@gmail.com> wrote:
> @Juvier, @yq Zhang
>
> In your approach, when you are asked pop_front() you keep popping from
> one stack and pushing them to another and then from the other pop the
> top element. What happens is this top element happens to have been the
> Min element?Example
>
> stack1 {(2,2),(4,2),(3,2),(6,2)} (a,b) = ( element, min)
>
> then you are asked pop_front(), you push to another stach like below
>
> stck2: {(6,2),(3,2),(4,2),(2,2)}.
>
> Then you remove (2,2)! Ok. But all elements in your stack2 still say
> "2" is the min element. But "2" is no more in the "queue" (or for that
> matter in the stacks we are using).
>
> On Jan 4, 9:07 am, yq Zhang <zhangyunq...@gmail.com> wrote:
> > @sourav,
> >
> > As Juvier++ pointed out, it's an **amortized** O(n) algorithm. That's
> > because each element can be at most popped twice.
> >
> > Thanks
> > Yq
> >
> > On Mon, Jan 3, 2011 at 11:20 AM, sourav <souravs...@gmail.com> wrote:
> > > @yq Zhang,
> >
> > > To pop if you are going to "pop all from first stack and push into the
> > > second stack", then does your operation remain "constant time"? Please
> > > note that we need constant time implementation for the 3 functions
> > > pop_front, push_rear and get_min(). Goint by your approach, not all of
> > > them are constant time.
> >
> > > Thanks,
> > > Sourav
> >
> > > On Jan 3, 9:44 pm, yq Zhang <zhangyunq...@gmail.com> wrote:
> > > > Push into one stack. When pop first pop all from the first stack and
> push
> > > > into the second stack. Then pop from the second stack
> > > > On Jan 3, 2011 7:42 AM, "MOHIT ...." <mohit...@gmail.com> wrote:
> >
> > > > > if only two stack are used but how pop_front is get?
> >
> > > > > suppose if element comes in order
> >
> > > > > 12 15 4 3 7 20
> > > > > then in min queue
> > > > > 1. 12 (12)
> > > > > 2. 12 12 (12,15)
> > > > > 3. 12 12 4 (12,15,4)
> > > > > 4.12 12 4 3 (12,15,4,3)
> > > > > 5.12 12 4 3 3 (12,15,4,3,7)
> > > > > 6.12 12 4 3 3 3 (12,15,4,3,20)
> >
> > > > > we can get min in constant by pop of stack but how pop front will
> work
> > > > using
> > > > > two stack only in constant time?
> >
> > > > > --
> > > > > You received this message because you are subscribed to the Google
> > > Groups
> >
> > > > "Algorithm Geeks" group.> To post to this group, send email to
> > > algoge...@googlegroups.com.
> > > > > To unsubscribe from this group, send email to
> >
> > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> >
> > > <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@googlegroups.com>
> >
> >
> > > > .> 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 algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> >
> > > .
> > > 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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> 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 algoge...@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.
