codebytes: Implement a stack whose push, pop and min operations all operate in O(1) time.

codebytes: Implement a stack whose push, pop and min operations all operate in O(1) time.

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

Algorithm:

1. Each stack element stores the value of that element and an index of the element that will be the lowest if the current element was removed.
2. int mI (field in class Stack) stores the index of the smallest element in the stack.
3. When we add an element we set it's lowest index value field to mI. If current element is smaller than lowest, mI is set to current index.
4. When we remove an element, if it is the mI index, we set mI to the local mI stored in that element.

Read full article from codebytes: Implement a stack whose push, pop and min operations all operate in O(1) time.