@bittu : In your first approach which u pointed out : What if the minimum element is poped out of the stack ?? We may have to search the whole stack to get the minimum element. ---- O(n) in worst case
In your second approach which u pointed out : If u use 2 stacks, consistency of 2 stacks in a problem and also we may have problems if we have duplicate problems. The complexity may be high if we use this approach. Just point out whats the complexity of ur approach !!!! On Wed, Jun 29, 2011 at 3:41 PM, bittu <[email protected]> wrote: > @juver++ correct > > @ankit you can see here > > 1st Approach . > You can implement this by having each node in the stack keep track of > the minimum beneath itself. Then, to find the min, you just look at > what the top element thinks is the min.When you push an element onto > the stack, the element is given the current minimum. It sets its > “local min” to be the min. > The disadvantage of above algo is that if we have a large stack, we > waste a lot of space by keeping track of the min for every single > element. > > 2nd Approach(Use Two Stack) so We can (maybe) do a bit better than > this by using an additional stack which keeps track of the mins. > it is also good If many elements have the same local min, then we’re > keeping a lot of duplicate data. so when we will push the value then > we will push in 2nd stack as well. while popping if value is equal to > min then we will remove it from 2nd stack. > > Hope It Will Help.:) > > > > Thanks > Shashank "I Don't Do Code to Code But I Do Code to Build Product" > Computer Science & Engineering > Birla Institute of Technology,Mesra > > -- > 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.
