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