For using a stack in order to achieve O(n) time, we can modify push and pop as follows(assuming we want max): While pushing, compare the top of the stack with the element to be pushed(say x). If x>top, just push normally. Else, pop elements until top>x. Keep an eye on the border cases as well. Thus top will always be containing the maximum, which can be retrieved obviously in O(1) time. Similar algo for pop can be formulated. regards.
On Tue, Jul 17, 2012 at 9:19 AM, Tushar <tushicom...@gmail.com> wrote: > can you please elaborate on usage of stack to do it in O(1)? > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/8jTvBVdzsmYJ. > > 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.
