Nerd Paradise : Coding Interview 6: Constant Time Stack with GetMin

Nerd Paradise : Coding Interview 6: Constant Time Stack with GetMin

"Create a datastructure that is a stack with Push, Pop commands that work in constant time. Additionally, there should be another command called GetMin which returns the smallest element in the stack."

If you have a collection of things, and you want to find the smallest element in it, you have to iterate through the collection to find it. Generally. This may give you the impression that Push and Pop are O(1) operations and GetMin is O(n). However there are better ways than brute force.

Because this collection is limited to two specific operations that you can implement any way you want, the first reaction is to keep track of a minimum and update it when you push a number larger than the minimum. This is a O(1) operation. However, popping a number that's a minimum will require you to go through the collection and re-calculate the new minimum. The simple implementation is O(n) but only in cases when the minimum is popped. All other cases are O(1) as well. This is a good solution for most cases, and can be optimized to O(log n) if you try hard enough.

But the question deals with a stack. The stack has a unique quality that any state of the stack can be tracked alongside the element in the stack. Imagine an implementation where you store tuple'd pairs in the stack instead of just integers. The first number in the tuple is the number you're pushing into the stack. The 2nd number is the minimum of the stack when that number was pushed. Once you pop a tuple, you're left with an accurate min at the new top of the stack.

Read full article from Nerd Paradise : Coding Interview 6: Constant Time Stack with GetMin