@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 <ecstasy.piy...@gmail.com> 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 <jagadish1...@gmail.com> 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 <ecstasy.piy...@gmail.com> 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 <jagadish1...@gmail.com> 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 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?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 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?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 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?hl=en.
