@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.
