[Solution]Problem 49:Min Stack[Google]

Data Structure Design

To learn more about the newsletter, check our detailed About Page + FAQs

To help me understand you better, please fill out this anonymous, 2-min survey

---

I hope you had a great time solving the question I shared. As mentioned yesterday, this is a question that will help you beyond just your interviews and competitive programming. You will often find yourself coming up with custom classes to fill your needs. Therefore, this is not a solution you want to miss.

Any guesses on what my solution does?

If you struggled with this question, don’t worry. If you missed it I’m running an awesome 50-week special. Using the button below, You can now get this newsletter for 50% off.

This amounts to the low daily cost of 11 INR or 0.14 USD.

This problem can be found as problem 155. Min Stack on Leetcode.

Problem

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 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
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

Constraints:

• -231 <= val <= 231 - 1

• Methods pop, top and getMin operations will always be called on non-empty stacks.

• At most 3 * 104 calls will be made to push, pop, top, and getMin.

You can test your solution here

Not only are my explanations clear and helpful, they are also fun to read. Don’t miss out on them.

[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or by Email:

Venmo: https:/ount.venmo.com/u/FNU-Devansh

Paypal: paypal.me/ISeeThings

Or you can sign up for a Free Trial Below. Since the reception has been great, I got a special offer for y’all. You can get this newsletter free for 2 months, just by using the button below-

Step 1: Analyzing our needs

When it comes to DSA design questions, a good first step is to simply evaluate the DSA we already have at our disposal. Taking a bird’s eye view to look at what we have and how they fit our needs allows you to piece the solution together without having to do much trial and error. The worst thing in your interviews, competitive programming contests or assignments is to rush into the problem because you have a half-hearted understanding of the problem. This will cause you to waste a lot of time and energy and will look terrible to your interviewer. It’s better to take it slow and smooth, rather than rushing it and ending up stuck.

So going over the question needs, is there a Data Structure that stands out to be particularly useful to our needs? It’s not going to shock anyone to notice that in a question called Min Stack, a Stack would be very helpful. Indeed, a stack would handle 3 out of the 4 required operations. The getMin functionality is what makes this problem so tricky. Solving that will allow us to find the solution to this problem.

The reason why this question is so interesting is that there are multiple ways to solve the functionality. The most efficient way requires some insight that is easily missed. So make sure you follow this solution closely and understand every step. We will first build the working (but not super efficient) solution and use that to create our speedy solution.

Remember, to get to the efficient solution, it’s important to first have a working slow one. Going straight for the fastest one will leave you open to mistakes.

Step 2: Sketching out the Minimum Functionality

Let’s start looking into the getMin method and figure out some nuances of the operations. Let us see how the function would interact with the other object methods.

Picking the low-hanging fruit first, it should be clear that the top() method will not really interact with getMin(). Clearly, only the push and pop functions are relevant. And that makes sense. They are what modify the stack, and thus potentially change the minimum value.

Let’s see how each of them will interact with our gM method.

The push

When we push, we’re potentially introducing a new min value in our mS (minStack). To check for this, we’ll need to have immediate access to our current stack min value. The simplest way to do this is a variable tracking the min value. Is our solution really that easy?

The pop

Upon popping, we potentially remove the minimum value in our mS. In this case, we’d need to be able to update our new value without going through the previously seen values.

This should make it clear why simply tracking the min value at any given time will not be enough. Instead of what we would need is to track the minimum seen up to a layer, for every layer of our mS. This way when we pop the min value, our next layer will automatically have the next lowest value. Let’s cover this with an example.

Imagine we had the following values as input- [1,2,-1,3]. Then our minimum layer collection would look like [1,1,-1,-1]. We call pop. Now we’ve removed 3. We will also remove the last -1. Now we’re left with [1,1-1] for the mins and [1,2,-1] for the stack. We pop again and now our minimum changes. Tracking the min value up to this point pays off because we already know what the minimum value remaining is (1 in this case). We didn’t have to go through the remaining parts of the string.

Let’s start sketching out the implementation of the DS, keeping in mind what we’ve discussed.

Step 3: Creating our base solution

We’ve already discussed the mechanics of the mS. Let’s cover the implementation side of it. First off, we need to talk about the initialization. Clearly, we will need two stacks. The first will be our normal stack, containing our input. The second will go over the inputs, and tell us the minimum value we have seen upto that particular level. In other words

min_Stack[i]= min(Stack[:i+1]) #assume bounds will hold up

To those not familiar with List Slicing notation. Source

As discussed, for [1,2,-1,3], the min would be [1,1,-1,-1]. These would both be stacks to accomodate the LIFO nature. Thus our initalization will be coded up like this-

def __init__(self):
        self.stack = []
        self.minStack = []

The push to the normal stack is relatively straightforward. The interesting part comes in the push to our minStack. Take a look at it, and see if you can figure out why we’re doing it the way we are.

    def push(self, val: int) -> None:
        self.stack.append(val)
        val = min(val, self.minStack[-1] if self.minStack else val)
        self.minStack.append(val)

Simply put, we want to add the minimum up to the layer. That might be the new value OR it could be the minimum we have seen so far (min till last layer). We know it will be the minimum of these. Next let’s look at the pop function.

def pop(self) -> None:
        self.stack.pop()
        self.minStack.pop()

Yes, that simple. That is the beauty of doing things this way. Since we’re pushing the min value to both stacks every time, we don’t need to worry about any size mismatches and funny events in operations. Since, our top and getMin are fairly trivial at this point, I will combine all the functions we’ve covered, so that you can copy them easily.

class MinStack:
    def __init__(self):
        self.stack = []
        self.minStack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        val = min(val, self.minStack[-1] if self.minStack else val)
        self.minStack.append(val)

    def pop(self) -> None:
        self.stack.pop()
        self.minStack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minStack[-1]

You can copy this code into Leetcode and run it as is. And it will be accepted. However, this is not the best solution. This solution has a few redundancies. Fixing them will make your solution really purr (and allow you to stand out). From an interview perspective, think of it as the difference between a maybe and a strong YES!! Which would you rather be?

The interviewer after you present them with the solution I’m about to show you. Any WWE fans in my readership? When I was a kid, I wanted to be a WWE champion. My brother and I were going to enter the tag-team division.

Remember tech often operates at a large scale. Optimizing a little bit, can save a lot of costs or generate a lot of revenue. We’ve discussed this idea in more detail in our Math Monday on Scale, linked here.

Are you ready to learn about this great solution? Trust me, there are no weird language-specific tricks. No esoteric algorithms that you would find in an upper-level Math Course. Nothing you would not be able to replicate in your interview. Let’s get into it.

Step 4: Trimming the Fat

Let’s look at all the components of our solution, step by step. And remove the waste.

Looking at the initialization first, it seems a little wasteful how we track the same minimum value multiple times. If there was a way to keep our minStack smaller, tracking one min value only once per appearance (remember we can have repeating values in the input. If we have our min value show up multiple times, our minStack should reflect that).

Leveraging this insight, let’s look at the push. If we can optimize that, then our minStack will become smaller (we won’t add values for every input). So how do we optimize the push operation?

It’s easier than you’d think. Clearly, we want to tweak our protocol and only add to our mS only when necessary. Let’s keep it simple and do that.

def push(self, val: int) -> None:
        self.stack.append(val)
        if val <= self.minStack [-1]: #we have equality to check for repeating min value
            self.minStack .append(val)

We use val <= self.minStack [-1] instead of val < self.minStack [-1] to account for repeating min values.

However, keep in mind, that this will break our pop function. We have to adjust our pop to remove from the mS only when we actually change the minimum. How do we do that? Pop from the normal stack. If this value is equal to our minimum, then pop from the mS. Otherwise, leave it be.

def pop(self) -> None:
        idx = self.stack.pop()
        if idx == self.minStack [-1]: #we're popping the min
            self.minStack .pop()

Our pop and top stay the same. This is all great. We’ve been super efficient now. But there is one teensy little problem. This solution will break on running. Try to think about when and why.

Think real hard about it. I’ll tell you soon.

But first, think for yourself. No scrolling down w/o thinking. That’s cheating.

I can trust you can’t I? Especially you, Shaz. I have my eyes on you. So I’ll catch you cheating. You hear that, Shaz?

Alright, I’ll tell you. This solution will break at the start of every run. The first time we call push, self.minStack is empty. We have the check val <= self.minStack [-1]

This will be messy. So what can we do?

There are many ways to approach the solution. You can use a global state variable to track the operations. You can use a bunch of conditionals. I have something much easier. Take a look-

def __init__(self):
        self.stack  = []
        self.minStack = [float("inf")]

When it comes to our minStack, we initialize it with a positive infinity. We know that any input val has to be lesser than this. So we will never run into any errors when adding the first value and updating our minimum. As we’ve already talked about, everything else will be smooth like butter. Time to put all this together in our code

Step 5: Putting it all together

We’ve covered everything important up to this point. So the code should not come as a shock. I’m just putting everything into one place so that y’all can look it together/copy it easily.

class MinStack:

    def __init__(self):
        self.stack  = []
        self.minStack = [float("+inf")]

    def push(self, val: int) -> None:
        self.stack.append(val)
        if val <= self.minStack [-1]: #we have equality to check for repeating min value
            self.minStack .append(val)
            
    def pop(self) -> None:
        idx = self.stack.pop()
        if idx == self.minStack [-1]: #we're popping the min
            self.minStack .pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minStack[-1]        

Time Complexity- O(1) for every function. O(N) to run through the input.

Space Complexity- O(N). Worst case is when we get a lot of numbers in descending order, without any pops. In this case, we store all the values in both stack and minStack.

Loved the solution? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Reach out to me by replying to this email, in the comments, or using the links below.

Stay Woke. I’ll see you living the dream.

Go kill all,

Devansh <3

Reach out to me on:

Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/

My content:

Read my articles: https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd

Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75