yes i too think now that it should work..but on every push/pop we will need to update the other two stacks also which can be done in constant time..
On Fri, Oct 8, 2010 at 12:58 AM, tech rascal <[email protected]>wrote: > I think saurabh gupta is rite.....if v take 2 extra stacks ...1 for min and > 1 for max, thn some space wud b saved. > for the above example .........max_stack wud b- > > ------------------------>top > 45 56 66 76 44343 > > and min_stack wud b- > > --------------->top > 45 22 3 2 -999 > > so, here v need 2 save only 5 elements in max_stack, 5 elements in > min_stack and 15 elements in full_stack ( acc 2 above example only), hence > total=25 elements..........othrwise if u do it by taking only 1 stack thn u > need space for ..15X3 (45)elements. > > tell me if I am wrong.. > > On Thu, Oct 7, 2010 at 11:49 PM, saurabh singh <[email protected]>wrote: > >> Sorry but I have still not got the solution u have tried to propose here. >> Firstly the space complexity remain O(n) only what I said. >> >> To understand thing u said better lets take an example of stack with >> following entries >> >> --------------------------->top >> 45 22 56 44 55 3 2 4 -999 4 2 45 66 76 44343 >> >> how will your second stack look like and how will the push/pop/min/max >> will work here ? >> >> >> >> On Thu, Oct 7, 2010 at 11:33 PM, Saurabh Gupta < >> [email protected]> wrote: >> >>> >>> >>> On Tue, Oct 5, 2010 at 9:47 AM, saurabh singh <[email protected]>wrote: >>> >>>> elaborate plz >>> >>> >>> For every new element in stack, you need thrice of space to store the min >>> and max elements also. This has the effect that at state of stack, you can >>> get the min and max till that point. Instead of this, maintaining a new >>> stack for min elements would be much more efficient in terms of memory since >>> in that all the number of elements would be lesser than the main one. >>> >>> so, basically in your solution, the size of object will be three times >>> bigger than the data type which can hold the number otherwise. >>> >>> >>>> >>>> On Tue, Oct 5, 2010 at 9:42 AM, Saurabh Gupta < >>>> [email protected]> wrote: >>>> >>>>> In this method, the extra memory is used. In fact, maintaining a >>>>> separate stack of min and max would consume lesser memory than this. >>>>> >>>>> On Thu, Sep 30, 2010 at 12:17 AM, saurabh singh < >>>>> [email protected]> wrote: >>>>> >>>>>> You will just need to see what is min and max available on the current >>>>>> top before push. in case of pop u dnt need to do anything... >>>>>> >>>>>> consider this array imp of stack >>>>>> each array index is stored with this object : {data, min_till_here, >>>>>> max_till_here} >>>>>> >>>>>> ------------------------------------------------------------->Top >>>>>> [{4,4,4} , {2,2,4}, {7,2,7} , {-6,-6,7}, {1,-6,7}, {9,-6,9}] >>>>>> >>>>>> >>>>>> >>>>>> So if u push say 20 then at top u see whats max and min till now. >>>>>> since curr min (-6) is smaller than 20 so min remains unaffected and >>>>>> since >>>>>> curr max (9) is smaller than 20 so curr max becomes 20. Hence the object >>>>>> at >>>>>> top in stack looks like {20,-6,20} >>>>>> >>>>>> >>>>>> On Wed, Sep 29, 2010 at 10:18 PM, albert theboss < >>>>>> [email protected]> wrote: >>>>>> >>>>>>> >>>>>>> when we pop out something .... >>>>>>> we need to find the max min again if max or min is popped out... >>>>>>> this ll take again O(n) to find max and min.... >>>>>>> >>>>>>> Correct me if am wrong.... >>>>>>> >>>>>>> -- >>>>>>> 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]<algogeeks%[email protected]> >>>>>>> . >>>>>>> For more options, visit this group at >>>>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>>>> >>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> Thanks & Regards, >>>>>> Saurabh >>>>>> >>>>>> -- >>>>>> 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]<algogeeks%[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]<algogeeks%[email protected]> >>>>> . >>>>> For more options, visit this group at >>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>> >>>> >>>> >>>> >>>> -- >>>> Thanks & Regards, >>>> Saurabh >>>> >>>> -- >>>> 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]<algogeeks%[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]<algogeeks%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Thanks & Regards, >> Saurabh >> >> -- >> 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]<algogeeks%[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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Thanks & Regards, Saurabh -- 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.
