@don :
say you have 10 elements and the min is also pointing to the Top of
stack..(1,3,2,4,5,6,7,3,5,2,7)
what would be the output of
pop() followed by min()
On Mon, Sep 5, 2011 at 9:37 PM, Dave <dave_and_da...@juno.com> wrote:
> @Shravan: Memory is cheep. $15 or less per gigabyte. When we are
> talking about O(n), that allows n to get pretty large cheaply.
>
> Dave
>
> On Sep 5, 10:50 am, 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
> >
> > ...
> >
> > read more ยป- 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.
>
>
--
Rishabbh A Dua
--
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.
