@Shravan: Memory is cheep. $15 or less per gigabyte. When we are talking about O(n), that allows n to get pretty large cheaply.
Dave On Sep 5, 10:50 am, Shravan Kumar <shrava...@gmail.com> wrote: > @Dave agreed > @Sandeep it works, but it takes more memory > > On Mon, Sep 5, 2011 at 9:15 PM, SANDEEP CHUGH <sandeep.aa...@gmail.com>wrote: > > > > > @dave : ya ryt.. > > @shravan ; my solution works for the case that dave has told.. so at every > > step we hav to push min.. > > > On Mon, Sep 5, 2011 at 9:11 PM, Dave <dave_and_da...@juno.com> wrote: > > >> @Shravan: You at least have to push equal mins on the min stack. > >> Otherwise, with the sequence 2, 1, 1, if you push only 2 and 1 onto > >> the min stack, then when you pop the first 1 from the data stack and > >> pop the 1 from the min stack, the top of the min stack is 2, but the > >> minimum in the data stack is 1. So you push 2, 1, 1 onto the min > >> stack. When you pop the first 1 from the data stack, you pop the first > >> 1 from the min stack, and still show the min = 1. > > >> Don's solution for data sequence 2, 3, 1, 1 would push (2,2) (3,2), > >> (1,1), (1,1) onto one stack, whereas you should push 2, 3, 1, 1 onto > >> the data stack and 2, 1, 1 onto the min stack, for a saving of one > >> stack item. For the sequence 1, 1, 1, 1, 1, 1, 1, you both would have > >> the same number of items stacked. > > >> Dave > > >> On Sep 5, 10:09 am, Shravan Kumar <shrava...@gmail.com> wrote: > >> > @sandeep > > >> > You don't need to store duplicate elements in stack2. When you want min > >> > return top element. When an element is popped from stack1, pop stack2 > >> only > >> > if it is equal to popped stack1 element. > > >> > On Mon, Sep 5, 2011 at 8:21 PM, SANDEEP CHUGH <sandeep.aa...@gmail.com > >> >wrote: > > >> > > 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.-Hide quoted text - > > >> > - Show quoted text - > > >> -- > >> 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 > > ... > > read more »- Hide quoted text - > > - Show quoted text - -- 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.