Solve the Min Stack Puzzle

Welcome to another article on solving programming problems in Swift. Here, I’ll be covering the Minimum Stack problem.

Yalla, let’s begin.

Problem Statement

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

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Example:

    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.getMin(); // return -3
    minStack.pop();
    minStack.top();    // return 0
    minStack.getMin(); // return -2

Problem Analysis

After reading the problem statement, it’s important to keep in mind that the time complexity for each function should be O(1). Right off the bat, we know either an Array or LinkedList is a go-to data structure for creating a Stack. For simplicity, I’ll use an array.

Let’s analyze each requirement to implement the MinStack class.

MinStack() initializes the stack object.

Very self-explanatory, we simply initialize an array.

void push(int val) pushes the element val onto the stack

Appending an element to an array is a constant operation.

void pop() removes the element on the top of the stack.

Removing the last element of an array using is a constant operation.

int top() gets the top element of the stack.

Returning the last element of an array is a constant operation.

Notice the first 4 requirements are very straightforward - we’re simply creating a Stack programmatically using an array. Now it’s time to analyze the final requirement:

int getMin() retrieves the minimum element in the stack.

This is where things get interesting. Without thinking about code, let’s visualize how getMin() works by walking through an example.

**Step 1**:
Push -2. Since -2 is the only value, the minimum is -2.

**Step 2:**

Push 0 and compare it to the current minimum. -2 is still the minimum.

**Step 3:**
Push -3 and compare it to the current minimum. -3 is now the new minimum.

**Step 4:**

Perform a pop operation, which removes -3. Now the minimum is -2.

Did you notice a pattern? With every push operation, a comparison is done to determine the minimum value. Also notice a trail of minimum values is needed, especially as highlighted in step 4 with the pop operation. Now for the golden question - how can we keep track of minimum values using an O(1) time complexity?

There are several ways, but my approach is using tuples. Simply instantiate an array of tuples - one holding the current value and the other holding the minimum value.

Enough talk, let’s code!

Solution

Min Stack Initialization

Here we initialize our array in the MinStack class.

Push Operation

As highlighted from the problem analysis, an empty stack will push the value as both the current and minimum value. Otherwise, compare the new value to the top's minimum value and determine which is the new minimum.

Pop Operation

Straightforward operation - just remove the last array element.

Top & Get Minimum

For the top() function, just return the currentValue of the last element in the array. Same with the getMin() function, but instead return the minValue.

Final Solution

Putting it all together, here’s our solution to this problem.

Results

Time Complexity: O(1)

LeetCode Performance:

Stellar runtime and decent memory performance 👏🏼

For any comments and questions on this post, follow up on Twitter.

Make sure to share this article. Appreciate you reading through my blog and until next time.