Min Stack

Medium

Asked by:

+12

More companies

199 views

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.

Try coding it in LeetCode

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:

Are there any constraints on the range of integer values that can be pushed onto the stack?
What should `getMin()` return if the stack is empty?
Can the stack store duplicate values, and how should duplicates be handled when retrieving the minimum?
What is the expected behavior of `pop()` or `top()` when the stack is empty?
Are there any constraints on the total number of operations (push, pop, top, getMin) that will be performed on the stack?

Brute Force Solution

Approach

The brute force approach to this problem involves checking every single number that has been added to our special stack to find the minimum value. We do this every time we need to know what the minimum is.

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

When we want to add a new number, we just put it on top of our existing numbers.
When we want to find the smallest number, we look at all the numbers currently in our stack, one by one.
We keep track of the smallest number we've seen so far as we look at each number.
Once we have examined every number, the one we kept track of as the smallest is our answer.
When we want to remove the top number, we simply take it off the top of our stack.

Code Implementation

class MinStackBruteForce:

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

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

    def pop(self):
        # Ensure we don't pop from an empty stack
        if self.stack_elements:
            self.stack_elements.pop()

    def top(self):
        # Return the top element without removing it
        if self.stack_elements:
            return self.stack_elements[-1]
        return None

    def get_min(self):
        # We need to iterate through all elements to find the minimum
        if not self.stack_elements:
            return None

        minimum_value_found = self.stack_elements[0]
        # Check every element to find the absolute smallest
        for element_in_stack in self.stack_elements:
            if element_in_stack < minimum_value_found:
                minimum_value_found = element_in_stack
        return minimum_value_found

Big(O) Analysis

Time Complexity

O(n) – When adding an element, it's a constant time operation, O(1). When removing an element, it's also a constant time operation, O(1). The critical operation is finding the minimum. Since we iterate through all 'n' elements currently in the stack to find the minimum, this operation takes O(n) time. As finding the minimum can be called frequently, the overall time complexity for the getMin operation is O(n). Thus, the dominant factor is the getMin operation.

Space Complexity

O(1) – The provided brute force approach to the Min Stack problem utilizes a single stack data structure to store the elements. When finding the minimum, it iterates through the existing elements but does not allocate any new data structures that grow with the number of elements (N). The only auxiliary space used is for a few variables to keep track of the minimum value during iteration, which is constant. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The goal is to create a special kind of stack that can quickly tell you the smallest number currently inside it. The trick is to keep track of not just the numbers themselves, but also what the smallest number was when each number was added.

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

Imagine you have two separate storage areas. One is for the numbers you are actively putting into your stack.
The other storage area is specifically for keeping track of the smallest number seen so far at each step.
When you add a new number to the main storage, you also look at the current smallest number recorded. You then add either the new number itself, or the previous smallest number, whichever is smaller, to the smallest-tracker storage.
This way, the top of the smallest-tracker storage always holds the smallest number that is currently in the main storage.
When you remove a number from the main storage, you also remove the corresponding smallest number from the smallest-tracker storage.
To find the minimum, you simply look at the very top of the smallest-tracker storage.

Code Implementation

class MinStack:

    def __init__(self):
        self.main_stack_elements = []
        self.minimum_tracker_stack = []

    def push(self, value_to_push):
        self.main_stack_elements.append(value_to_push)
        # When pushing, we need to record the minimum up to this point.
        if not self.minimum_tracker_stack:
            self.minimum_tracker_stack.append(value_to_push)
        else:
            # We store the smaller of the new value or the current minimum.
            current_minimum = self.minimum_tracker_stack[-1]
            self.minimum_tracker_stack.append(min(value_to_push, current_minimum))

    def pop(self):
        if self.main_stack_elements:
            self.minimum_tracker_stack.pop()
            # Removing an element also requires removing its corresponding minimum tracking.
            return self.main_stack_elements.pop()
        return None

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

    def getMin(self):
        # The minimum is always at the top of the separate minimum tracking stack.
        if self.minimum_tracker_stack:
            return self.minimum_tracker_stack[-1]
        return None

Big(O) Analysis

Time Complexity

O(1) – The approach uses two stacks, one for the actual data and one to track the minimum element at each step. When pushing an element, we push the new element onto the data stack and the minimum of the new element and the current minimum onto the min-tracking stack. When popping, we pop from both stacks. When getting the minimum, we simply peek at the top of the min-tracking stack. All these operations involve a constant number of stack operations, regardless of the number of elements (n) currently in the stack. Therefore, each operation takes constant time.

Space Complexity

O(n) – The solution uses two storage areas: one for the main numbers and another to track the minimum at each step. Both of these storage areas will store an entry for each element pushed onto the stack. If 'n' is the number of elements in the stack, the auxiliary space required by these two storage areas grows linearly with 'n'. Therefore, the space complexity is O(n).

Edge Cases

Case	How to Handle
Calling pop, top, or getMin on an empty stack	The implementation should raise an error or return a sentinel value (e.g., None or an exception) to indicate an invalid operation.
Pushing a new minimum value	The solution must update the stored minimum to the new value, ensuring getMin() always reflects the current minimum.
Popping the current minimum value	The solution needs to correctly track the previous minimum value to maintain accurate getMin() results.
Stack with only one element	Pushing and then immediately popping or getting the minimum should function correctly.
Stack with all identical elements	The minimum should remain constant, and pop operations should correctly update to the same previous minimum.
Stack with negative numbers and zero	The comparison logic for minimums must handle negative values and zero correctly.
Extremely large number of pushes leading to memory limits	The solution's space complexity should be considered; using an auxiliary stack for minimums is generally efficient.
Pushing values that approach integer limits	Ensure the chosen data type for storing stack elements and minimums can accommodate the full range of potential input values without overflow.

Calling pop, top, or getMin on an empty stack

How to Handle:

The implementation should raise an error or return a sentinel value (e.g., None or an exception) to indicate an invalid operation.

Pushing a new minimum value

How to Handle:

The solution must update the stored minimum to the new value, ensuring getMin() always reflects the current minimum.

Popping the current minimum value

How to Handle:

The solution needs to correctly track the previous minimum value to maintain accurate getMin() results.

Stack with only one element

How to Handle:

Pushing and then immediately popping or getting the minimum should function correctly.

Stack with all identical elements

How to Handle:

The minimum should remain constant, and pop operations should correctly update to the same previous minimum.

Stack with negative numbers and zero

How to Handle:

The comparison logic for minimums must handle negative values and zero correctly.

Extremely large number of pushes leading to memory limits

How to Handle:

The solution's space complexity should be considered; using an auxiliary stack for minimums is generally efficient.

Pushing values that approach integer limits

How to Handle:

Ensure the chosen data type for storing stack elements and minimums can accommodate the full range of potential input values without overflow.