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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
