@don : say you have 10 elements and the min is also pointing to the Top of stack..(1,3,2,4,5,6,7,3,5,2,7)
what would be the output of pop() followed by min() On Mon, Sep 5, 2011 at 9:37 PM, Dave <[email protected]> wrote: > @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 <[email protected]> wrote: > > @Dave agreed > > @Sandeep it works, but it takes more memory > > > > On Mon, Sep 5, 2011 at 9:15 PM, SANDEEP CHUGH <[email protected] > >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 <[email protected]> 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 <[email protected]> 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 < > [email protected] > > >> >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 <[email protected]> > 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 < > > >> > >> [email protected]> 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 < > > >> [email protected]>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 <[email protected]> > 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 <[email protected]> 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 > [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. > > > > >> > >>>> -- > > >> > >>>> 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 > [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. > > > > >> > >>> -- > > > > >> > >>> **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* > > >> > >>> <[email protected]> > > > > >> > >>> -- > > >> > >>> 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. > > > > >> > > -- > > >> > > 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.-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 [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 > > > > ... > > > > 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 [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. > > -- Rishabbh A Dua -- 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.
