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 normal popping elements ,pop both of the stacks and get the element
popped from original stack (say element is o) and min stack (say element is m).
if(o&e ate same )
return poped element.
else
{
if(o<m)
{
while(o<m)
o=normal_stack.normal_pop()
}
push element m on minstack
and return o;
}
minpop() is as follows
To find minimum just get the top element of the minstack.
On 6/24/11, ross <[email protected]> wrote:
> @Piyush:
> Dude, that method u suggested wont work ...
> It works for stacks because, while deletion of an element, We may
> verify if it is in the top of second stack and delete it..
> (Since both the data structures are LIFO)
> Here in this case, if u delete, you cannot remove the top of stack and
> delete an element in the queue...
>
> eg: 1 22 3 44
> stack contains(minnm) : 1
> if u delete 1, then u pop it from the stack and minm must be 2
> I doubt if this problem has a solution.
> Correct me if i am wrong.
>
>
> On Jun 24, 3:33 pm, Piyush Sinha <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 [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.
>>
>> > > --
>> > > *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 [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.
>>
>> --
>> *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 [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.
