LeetCode Q155: Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Solution:

The essence of this question is to solve the problem of getting minimum element in remaining stack. To solve it we need to keep track the min in current stack. So, each entry in the stack have to domains, first one is used to save value of current element. the second domain contains the min value under the current element in the stack.

Round 2 solution: Anther way to track minimum element in current array is to use another stack. Similar to sliding window problem, the element inserted to the stack has to be strictly smaller or equal to current top element of the stack.