CODING

Day 29: The “Min Stack” Problem

Problem:

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.

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:

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

My Solution:

class MinStack:
   def __init__(self):
        self.topNode = None;
   class Node:
        def __init__(self, x = None):
            self.val = x
            self.min = x
            self.next = None
            
   def push(self, x):
        temp = self.Node(x);
        if (self.topNode is not None) :
            temp.next = self.topNode;
            if (x > self.topNode.min) :
                temp.min = self.topNode.min;
        self.topNode = temp;
   
   def pop(self):
        if(self.topNode is None):
            return None
        temp = self.topNode;
        self.topNode = temp.next;
   def top(self):
        if(self.topNode is None):
            return None
        return self.topNode.val
   def getMin(self):
        if(self.topNode is None):
            return None
        return self.topNode.min

Explanation:

This is similar to solving a stack except at every node in the stack, we also store the min element up to the point in the stack.

Every node in the stack, will store the current node value and the next pointer as usual. It will additionally store the current min value in the stack.

If the stack is empty, while we add our new node to the stack, our node is the min element in the stack.

However, if the stack is not empty, we use the top element in the stack to find the minimum value in the stack up to that point. We then compare it with the new element that is to be added to the stack.

So, to summarize, to add a new element to the stack, we will:

1. create a new node for our element Node(x)
2. calculate and set themin value of our node
3. set the node to point to the topmost element of the stack (using next)
4. store our new node as the top (topNode) of the stack.

To pop the topmost element from the stack, we advance the top pointer to point to the next element.

To retrieve the top value in the stack, we retrieve the value of the element on the top of the stack.

Similarly, to retrieve the minimum value in the stack, we use the min value of the element on the top of the stack.

And that’s it. That’s how you solve the “Min Stack” problem.

If you are interested in solving more problems, do follow 60 Days of Coding and join me on this journey.

If you would like me to solve and explain any problems, please add them as comments, along with a link to the problem description.

See you tomorrow!

Cheers!