+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 <nitin.garg.i...@gmail.com>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 <dondod...@gmail.com> 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 <sangeeta15...@gmail.com> 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 algogeeks@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.
>>
>>
>
>
> --
> 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 algogeeks@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.
>
--
**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*
<bagana.bharatku...@gmail.com>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
