In my earlier approach , if the element that is stored in "min" got popped
out then we have to search entire stack for min.. so i think my earlier
approach will not work.. tell me about that??
and i hav another approach.. also tell me about that also?
consider we have to push the elemnts 12 , 3, 15 ,8 ,2, 9
stack 1 stack 2
12
12
first 12 came , push in both
3
12
3
12
next 3 came , push 3 in first stack , and
push minumum ( stack1 top elem , stack2 top elem ) into stack2 ..
i.e 3 pushed to 2nd stack
15
3
12
3
3
12
now for all the numbers that are coming , push them
into first stack and push min of both stacks top elements into 2nd stack
min (15 , 3) --> 3 pushed to stack2
8
15
3
12
3
3
3
12
min (8,3) ---> 3 pushed to stack2
2
8
15
3
12
2
3
3
3
12
min(2,3) --> 2 pushed to stack2
9
2
8
15
3
12
2
2
3
3
3
12
min(9,2) -- > 2 pushed to stack2
so if at any time we want to print the minimum element , print the stack2
top element ,
and if pop() is performed on stack1 , then perform pop() operation on stack2
also .
after pop () on stack2 , stack2 top still contains the minimum element for
the rest of elements ..
On Mon, Sep 5, 2011 at 5:15 PM, kARTHIK R <[email protected]> wrote:
> +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 <
> [email protected]> 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 <[email protected]>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 <[email protected]> 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 <[email protected]> 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 [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.
>>>>
>>>>
>>>
>>>
>>> --
>>> 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 [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.
>>>
>>
>>
>>
>> --
>>
>> **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*
>> <[email protected]>
>>
>>
>> --
>> 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.
>>
>
> --
> 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.
>
--
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.
