+1 Don. Good Solution. We can't save space and time at the same time. Either
use extra space and do operations fast, or use O(1) for min, and if min is
popped, spend O(n) to spot the next min. Depends on the use case.
Karthik R,
R&D Engineer,
Tejas Networks.
On Mon, Sep 5, 2011 at 5:10 PM, bharatkumar bagana <
bagana.bharatku...@gmail.com> wrote:
> +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.
>
--
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.
