Problem:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. These are the operations you should implement for this data structure.

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

Example:

min_stack = new MinStack()
min_stack.push(-2)
min_stack.push(0)
min_stack.push(-3)
min_stack.get_min()   # Returns -3.
min_stack.pop()
min_stack.top()       # Returns 0.
min_stack.get_min()   # Returns -2.

1. Understand

# Design a minstack class with the following functionality:
# push(x) -- pushes element x onto stack
# pop() -- removes the element on top of stack
# top() -- returns the top element
# get_min() -- returns the min element in stack

## Example:
# min_stack = new MinStack()
# min_stack.push(-2)
# min_stack.push(0)
# min_stack.push(-3)
# min_stack.get_min()   # Returns -3.
# min_stack.pop()
# min_stack.top()       # Returns 0.
# min_stack.get_min()   # Returns -2.

2. Match

# Can use a list to implement the stack
# Since we're interested in also returning
# the minimum element, we can sacrifice space
# for time by storing tuples containing a pair:
# the element added to the stack and the current min

3. Plan / Pseudocode

# MinStack objects have a single class variable:
# a list of tuples
# Functions:
## push(x)
# If the list is empty, just append (x, x)
# since x will also be the current minimum
# Otherwise, check if x is less than the current min
# (will be located at [-1,1] or the second value
# in the last tuple in the list)
## pop()
# If the list isn't empty,
# remove the last item in list
## top()
# If the list isn't empty,
# Return element at [-1.0] or the first
# value in the last tuple in the list
## get_min()
# Return the element at [-1,1] or the second
# value in the last tuple in the list

4. Implement

5. Review

For the given example:

min_stack = new MinStack()
min_stack.push(-2)
min_stack.push(0)
min_stack.push(-3)
min_stack.get_min()   # Returns -3.
min_stack.pop()
min_stack.top()       # Returns 0.
min_stack.get_min()   # Returns -2.

We get the expected results:

6. Evaluate:

If I had just pushed the elements to the stack instead of a collection of the element and the current min, I would have had to have implemented the get_min function differently.

The get_min function would have had a time complexity of O(N) because I would have had to have traversed the entire list to compute the minimum value. However, by using additional space O(2N), still technically O(N), to store the current minimum every time a new element was pushed to the stack, the time complexity of the get_min function is constant time O(1) since it will always be in the last tuple in the list.