yes, on every push/pop there will be max 2 push/pop and 2 comparisons which
is ultimately O(1).
(only in case of 1st element of stack there will be 3 push/pop)
-Regards
Amit Agarwal
blog.amitagrwal.com
On Fri, Oct 8, 2010 at 9:31 AM, saurabh singh <saurabh.n...@gmail.com>wrote:
> 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 <techrascal...@gmail.com>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 <saurabh.n...@gmail.com>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 <
>>> saurabhgupta1...@gmail.com> wrote:
>>>
>>>>
>>>>
>>>> On Tue, Oct 5, 2010 at 9:47 AM, saurabh singh
>>>> <saurabh.n...@gmail.com>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 <
>>>>> saurabhgupta1...@gmail.com> 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 <
>>>>>> saurabh.n...@gmail.com> 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 <
>>>>>>> alberttheb...@gmail.com> 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 algoge...@googlegroups.com.
>>>>>>>> To unsubscribe from this group, send email to
>>>>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>>>>>> .
>>>>>>>> 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 algoge...@googlegroups.com.
>>>>>>> To unsubscribe from this group, send email to
>>>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
>>>>>> To unsubscribe from this group, send email to
>>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>>>> .
>>>>>> 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 algoge...@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>> .
>>>> 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 algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> 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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
