The basic idea would be to do push / pop the minimum in stack along with the push / pop elements. It is like maintaining a parallel stack of minimums. A naive implementation would involve two stacks. All operations should be O(1) time complexity.
On Tue, Oct 6, 2009 at 1:31 PM, Manisha <pgo...@gmail.com> wrote: > > I found this question in a interview blog. > > http://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html > Question No. 19 > > My understanding for "retrieve minimum in constant time" is, we should > be able to find the minimum element in stack and to remove (pop) it in > constant time. Correct me if I am wrong. > > My idea is to maintain a sorted linked list of items so that we can > return the minimum and delete it from linked list in o(1) time. > > Push operation: > Whenever a new items come, I will find the correct location for this > new item in the sorted linked list and insert this item in linked > list. Now I will take the address of this linked list item and push it > on stack. > > Pop operation: > I will take the linked list item address stored at stack[tos]. As I > have address, > I can delete the node from linked list as well. > > Retrieving minimum: > Return the first item from the sorted linked list. o(1) > But for popping this item address from stack, I need to reorganize the > complete stack. > It will have o(n) time and space complexity. > > Is there any way to improve it or other ways of solving it? > > > > > -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
