In my earlier approach , if the element that is stored in "min" got popped out then we have to search entire stack for min.. so i think my earlier approach will not work.. tell me about that??
and i hav another approach.. also tell me about that also? consider we have to push the elemnts 12 , 3, 15 ,8 ,2, 9 stack 1 stack 2 12 12 first 12 came , push in both 3 12 3 12 next 3 came , push 3 in first stack , and push minumum ( stack1 top elem , stack2 top elem ) into stack2 .. i.e 3 pushed to 2nd stack 15 3 12 3 3 12 now for all the numbers that are coming , push them into first stack and push min of both stacks top elements into 2nd stack min (15 , 3) --> 3 pushed to stack2 8 15 3 12 3 3 3 12 min (8,3) ---> 3 pushed to stack2 2 8 15 3 12 2 3 3 3 12 min(2,3) --> 2 pushed to stack2 9 2 8 15 3 12 2 2 3 3 3 12 min(9,2) -- > 2 pushed to stack2 so if at any time we want to print the minimum element , print the stack2 top element , and if pop() is performed on stack1 , then perform pop() operation on stack2 also . after pop () on stack2 , stack2 top still contains the minimum element for the rest of elements .. On Mon, Sep 5, 2011 at 5:15 PM, kARTHIK R <k4rth...@gmail.com> wrote: > +1 Don. Good Solution. We can't save space and time at the same time. > Either use extra space and do operations fast, or use O(1) for min, and if > min is popped, spend O(n) to spot the next min. Depends on the use case. > > > Karthik R, > R&D Engineer, > Tejas Networks. > > > > On Mon, Sep 5, 2011 at 5:10 PM, bharatkumar bagana < > bagana.bharatku...@gmail.com> wrote: > >> +1 sandeep >> @don: u'r sol is correct , but if the number of elements are very huge and >> the updated min is long numbers , then we are storing the min in each >> element ... its waste of memory ... >> if the # elements are less, then this is good sol.. >> >> >> >> On Mon, Sep 5, 2011 at 1:02 AM, Nitin Garg <nitin.garg.i...@gmail.com>wrote: >> >>> Don's solution is correct. >>> At each push() operation, you update the value of min element upto that >>> depth in stack. >>> Can be illustrated with the following example - >>> >>> >>> stack = {} >>> push(2) stack = {(2,2)} >>> push(3) stack = {(3,2),(2,2)} >>> push(1) stack = {(1,1),(3,2),(2,2)} >>> >>> where b in tuple (a,b) represents the min value upto current depth in >>> stack. >>> pop() and min() are straight forward. >>> >>> On Mon, Sep 5, 2011 at 12:48 AM, Don <dondod...@gmail.com> wrote: >>> >>>> Each element in the stack will contain not only its own value, but the >>>> min value at that depth of the stack: >>>> >>>> struct stackItemStruct >>>> { >>>> int value; >>>> int min; >>>> struct stackItemStruct *next; >>>> }; >>>> >>>> typedef struct stackItemStruct stackItem; >>>> >>>> class stack >>>> { >>>> public: >>>> stack(); >>>> void push(int v); >>>> int pop(); >>>> int min(); >>>> private: >>>> stackItem *_stack; >>>> }; >>>> >>>> stack::stack() >>>> { >>>> _stack = 0; >>>> } >>>> >>>> void stack::push(int v) >>>> { >>>> stackItem newItem = new stackItem; >>>> newItem->value = newItem->min = v; >>>> if (_stack && (_stack->min < v) ) >>>> newItem->min = _stack->min; >>>> newItem->next = _stack; >>>> _stack = newItem; >>>> } >>>> >>>> int stack::pop() >>>> { >>>> int result = 0; >>>> if (_stack) >>>> { >>>> result = _stack->val; >>>> stackItem *tmp = _stack; >>>> _stack = tmp->next; >>>> delete tmp; >>>> } >>>> return result; >>>> } >>>> >>>> int stack::min() >>>> { >>>> return _stack ? _stack->min : 0; >>>> } >>>> >>>> On Sep 4, 12:08 pm, Sangeeta <sangeeta15...@gmail.com> wrote: >>>> > How would you design a stack which,in addition to push and pop,also >>>> > has a function min which returns the minimum element?push,pop and min >>>> > should all operate in O(1) time >>>> >>>> -- >>>> 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. >>>> >>>> >>> >>> >>> -- >>> Nitin Garg >>> >>> "Personality can open doors... but only Character can keep them open" >>> >>> -- >>> 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. >>> >> >> >> >> -- >> >> **Please do not print this e-mail until urgent requirement. Go Green!! >> Save Papers <=> Save Trees >> *BharatKumar Bagana* >> **http://www.google.com/profiles/bagana.bharatkumar<http://www.google.com/profiles/bagana.bharatkumar> >> * >> Mobile +91 8056127652* >> <bagana.bharatku...@gmail.com> >> >> >> -- >> 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. >> > > -- > 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. > -- 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.