Min Stack

Medium

Snap

1 view

Topics:

Stacks

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:

-2³¹ <= val <= 2³¹ - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 10⁴ calls will be made to push, pop, top, and getMin.

Min Stack

Medium

Snap

1 view

Topics:

Stacks

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:

-2³¹ <= val <= 2³¹ - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 10⁴ calls will be made to push, pop, top, and getMin.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values that will be pushed onto the stack?
Will there be calls to `pop` or `top` when the stack is empty?
If the stack is empty when `getMin` is called, what should be returned or should an exception be thrown?
How many operations (push, pop, top, getMin) can I expect to be performed in total?
Are we optimizing for space complexity, or can I use additional data structures to help with the `getMin` operation?

Brute Force Solution

Approach

The brute force approach to the Min Stack problem involves storing all the stack's elements and then, when we need the minimum, searching through all of them. It's straightforward: keep everything and search when needed. This guarantees finding the minimum, but it's not very efficient.

Here's how the algorithm would work step-by-step:

When a new number comes in, just add it to a storage area where we keep all the numbers.
To get the smallest number so far, go through every single number in the storage area.
Compare each number to all the others to see which one is the smallest.
Return the smallest number that you found.

Code Implementation

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

    def push(self, value):
        self.stack_elements.append(value)

    def pop(self):
        if not self.stack_elements:
            return None
        return self.stack_elements.pop()

    def top(self):
        if not self.stack_elements:
            return None
        return self.stack_elements[-1]

    def getMin(self):
        # Need to handle the case where the stack is empty
        if not self.stack_elements:
            return None

        minimum_value = self.stack_elements[0]

        # Iterate through the stack elements to find the smallest one
        for element in self.stack_elements:

            if element < minimum_value:

                # Update the minimum if a smaller element is found
                minimum_value = element

        return minimum_value

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The push operation takes O(1) time as it simply appends the new element to the stack. The getMin operation iterates through all the elements currently in the stack to find the minimum. If there are n elements in the stack, getMin will iterate through all n elements once. Thus, the getMin operation has a time complexity of O(n).

Space Complexity

O(N) – The brute force approach stores all incoming numbers in a storage area. If we push N numbers onto the stack, this storage area will contain N elements. Therefore, the auxiliary space used is proportional to the number of elements pushed onto the stack, leading to a space complexity of O(N).

Optimal Solution

Approach

The problem is to create a special data structure that can quickly tell you the smallest number stored inside. To do this efficiently, we'll use an extra storage area to keep track of the current minimum value whenever we add or remove numbers.

Here's how the algorithm would work step-by-step:

When a new number is added, compare it to the current minimum value. If the new number is smaller or equal, store that number as the new minimum on top of our extra storage area. This way, we always know the smallest number seen so far.
If a number is removed and it happens to be the current minimum value, then also remove the corresponding minimum value from our extra storage area. The next value in the extra storage area then becomes the new minimum.
The top number in the extra storage area will always represent the current minimum value contained within the regular numbers, making it very quick to find the minimum at any time.

Code Implementation

class MinStack:

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

    def push(self, value):
        self.stack.append(value)
        # Only push to minimum_stack if smaller or equal
        if not self.minimum_stack or value <= self.minimum_stack[-1]:
            self.minimum_stack.append(value)

    def pop(self):
        # Need to pop from both stacks if the min is being popped
        if self.stack[-1] == self.minimum_stack[-1]:

            self.minimum_stack.pop()
        self.stack.pop()

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

    def getMin(self):
        # The top of the minimum stack is always the min
        return self.minimum_stack[-1]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The push operation involves a comparison and potentially adding an element to the min stack, both constant time operations. The pop operation involves removing elements from both stacks, also constant time. The getMin and top operations simply return the top element of a stack, again constant time. Therefore, regardless of the number of operations (n), each operation takes constant time.

Space Complexity

O(N) – The plain English explanation describes an extra storage area to keep track of the current minimum value. In the worst-case scenario, where all N added numbers are in descending order, each number will be a new minimum and stored in this extra storage area. Therefore, the auxiliary space used by the extra storage area grows linearly with the number of input numbers, N. This leads to a space complexity of O(N).

Edge Cases

Case	How to Handle
Pushing null onto the stack.	Reject null pushes to maintain data integrity or handle by converting to a defined value, such as zero depending on requirements.
Calling pop or top on an empty stack.	Raise an exception or return a null/default value indicating that the operation cannot be performed on an empty stack.
Pushing a large number of elements onto the stack, exceeding available memory.	The solution should be designed to handle potential memory overflow gracefully, possibly by pre-allocating memory or using dynamic memory allocation carefully or setting an upper limit.
Pushing integers close to the maximum or minimum integer values, potentially causing overflow or underflow when calculating the minimum.	Use a data type that can accommodate a wider range of values (e.g., long) or implement checks to prevent overflow or underflow during calculations.
A sequence of operations where all pushed values are the same.	The min tracking must correctly handle sequences where minimum doesn't change, and additional checks aren't needed as it operates normally.
A sequence of pushes and pops that result in an empty stack multiple times.	Handle empty stack conditions when calling top or getMin after a series of pops, potentially raising an exception or returning a default/null value.
Pushing values containing extreme negative values then asking getMin.	The solution must handle extreme negative values correctly when tracking the minimum, ensuring calculations and comparisons work as expected.
Calling getMin on an empty stack.	Return null or throw an exception if getMin is called when the stack is empty.