yeah memory will be a issue.. but if we want to use less memory.. then it
cannot be done in o(1)..
so the usual trade off space vs time... lol
On Mon, Sep 5, 2011 at 9:20 PM, Shravan Kumar <shrava...@gmail.com> wrote:
> @Dave agreed
> @Sandeep it works, but it takes more memory
>
> On Mon, Sep 5, 2011 at 9:15 PM, SANDEEP CHUGH <sandeep.aa...@gmail.com>wrote:
>
>> @dave : ya ryt..
>> @shravan ; my solution works for the case that dave has told.. so at every
>> step we hav to push min..
>>
>>
>> On Mon, Sep 5, 2011 at 9:11 PM, Dave <dave_and_da...@juno.com> wrote:
>>
>>> @Shravan: You at least have to push equal mins on the min stack.
>>> Otherwise, with the sequence 2, 1, 1, if you push only 2 and 1 onto
>>> the min stack, then when you pop the first 1 from the data stack and
>>> pop the 1 from the min stack, the top of the min stack is 2, but the
>>> minimum in the data stack is 1. So you push 2, 1, 1 onto the min
>>> stack. When you pop the first 1 from the data stack, you pop the first
>>> 1 from the min stack, and still show the min = 1.
>>>
>>> Don's solution for data sequence 2, 3, 1, 1 would push (2,2) (3,2),
>>> (1,1), (1,1) onto one stack, whereas you should push 2, 3, 1, 1 onto
>>> the data stack and 2, 1, 1 onto the min stack, for a saving of one
>>> stack item. For the sequence 1, 1, 1, 1, 1, 1, 1, you both would have
>>> the same number of items stacked.
>>>
>>> Dave
>>>
>>> On Sep 5, 10:09 am, Shravan Kumar <shrava...@gmail.com> wrote:
>>> > @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.- Hide quoted text -
>>> >
>>> > - Show quoted text -
>>>
>>> --
>>> 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.
