It’s been a while since I last posted an article on an algorithm and data structure problem. This time I decided to solve the Min Stack problem. In Min Stack you need to find the minimum element inside a stack in constant time.

An alternate question is Max Stack where you have to find the maximum element in a stack. Both are pretty similar conceptually.

The problem explicitly states that each stack method should run at constant time - O(1).

This is the problem statement:

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.

Before continuing, make sure you try this problem yourself.

We will create a class calling it MinStack and inside it we will have two arrays.

private var elements: [Int] = [] private var minElements: [Int] = []

The elements array will be our main stack where the user appends or pushes new elements into. The minElement array is going to act as a secondary stack which will be used to keep track of the minimum element value at different stages.

Let’s code the first method - push(x):

func push(x: Int) {
        elements.append(x)
        if minElements.count == 0 {
            minElements.append(x)
        }else {
            if let minElement = minElements.last, let lastElement = elements.last {
                if lastElement <= minElement {
                    minElements.append(lastElement)
                }
            }
        }
    }

In this method, we are appending or pushing the element passed in by the function argument to the main ‘elements’ array. Then if the minElements array is empty we are simply appending the passed element into it. This is to “warm up” both stacks.

The next time the user pushes an element, we will simply append it in the elements array however, we will apply some bit of logic before appending it to the minElements stack.

We are using last() method which comes by default with Array. This method returns the last element in the array. The element type returned is optional (if array is empty, nil will be returned). Therefore, we are safely unwrapping last elements from both arrays using If - let statements.

Once we get the elements, we are checking if the top element in the element stack is less than or equal to the top element in the minElement stack. If it is, that element is appended or pushed to minElements stack as well.

Next, let’s implement pop() method:

In this method we will be removing the top element in the stack. We will use the .popLast() method. This method removes the last element in the array and also returns that element.

func pop() {
        let popElement = elements.popLast()
        if let poppedElement = popElement, let minElementPop = minElements.last {
            if poppedElement == minElementPop {
                minElements.popLast()
            }
        }
    }

We grab the returned last element from the main elements stack, and then again check the top element of minElements stack and check if the popped element and the top element of minElements stack is equal or not. If they are equal, then the top element is removed from minElements stack as well.

The remaining two methods are top() and getMin() - in both these methods we are simply popping the last element in the arrays and returning them.

    func top() -> Int {
        return elements.last ?? 0
    }

    func getMin() -> Int {
        return minElements.last ?? 0
    }

The main thing here to notice is that the methods run at constant time. Nowhere inside any method did we iterated through the entire array - (this will be O(n)). With O(1) time complexity our algorithm works at constant time and not dependent to the size of the stack.