@sandeep
You don't need to store duplicate elements in stack2. When you want min
return top element. When an element is popped from stack1, pop stack2 only
if it is equal to popped stack1 element.
On Mon, Sep 5, 2011 at 8:21 PM, SANDEEP CHUGH <sandeep.aa...@gmail.com>wrote:
> 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 <k4rth...@gmail.com> 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 <
>> 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.
>>
>
> --
> 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.
