Min Stack

Medium

Microsoft

2 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.

Min Stack

Medium

Microsoft

2 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.

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 might be pushed onto the stack?
If `getMin` is called on an empty stack, what should I return or should an exception be thrown?
Are null or empty values allowed to be pushed onto the stack?
If multiple elements in the stack have the same minimum value, does `getMin` return any of them or a specific one?
How many `push`, `pop`, `top`, and `getMin` operations should I expect to be performed in sequence; is there a practical limit to the total number of calls?

Brute Force Solution

Approach

The brute force method for the Min Stack involves keeping track of all the numbers pushed onto the stack. Whenever we need the minimum, we'll simply look through all the numbers we've saved to find the smallest one.

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

When a new number is added to the stack, we save it in a separate list.
When we need to find the minimum number in the stack, we go through every number in that list.
We compare each number to the current smallest number we've found, updating the smallest if we find a smaller one.
After checking all numbers, the number we are left with is the minimum.

Code Implementation

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

    def push(self, value):
        # Add the new value to the stack list.
        self.stack_list.append(value)

    def pop(self):
        if self.stack_list:
            self.stack_list.pop()

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

    def getMin(self):
        # Handle the case where the stack is empty.
        if not self.stack_list:
            return None

        current_minimum = self.stack_list[0]
        # Iterate through all elements in the stack.
        for element in self.stack_list:

            # Compare the element with current minimum
            if element < current_minimum:

                current_minimum = element

        # The min has been found after comparison
        return current_minimum

Big(O) Analysis

Time Complexity

O(n) – The push operation takes O(1) time as it only involves appending to a list. The pop operation similarly takes O(1) time. However, the getMin operation iterates through the entire list of n elements currently in the stack to find the minimum value. Therefore, getMin has a time complexity of O(n).

Space Complexity

O(N) – The brute force solution described uses a separate list to store all the numbers pushed onto the stack. In the worst-case scenario, we push N numbers onto the stack, where N is the number of push operations. This results in the separate list growing to a size of N to store these numbers. Thus, the auxiliary space used is directly proportional to the number of elements in the stack. The space complexity is therefore O(N).

Optimal Solution

Approach

To efficiently find the minimum value at any point in a stack, we'll use an additional stack to track the minimums. Each time we push an element, we check if it's a new minimum and update the minimum stack accordingly. This allows us to retrieve the minimum in constant time.

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

Maintain two stacks: one for the elements themselves, and another specifically for tracking the minimum element at each stage.
When a new element is added to the main stack, compare it to the current minimum (if the minimum stack is not empty).
If the new element is less than or equal to the current minimum, also add it to the minimum stack. If the minimum stack is empty, the new element becomes the first minimum.
When an element is removed from the main stack, check if it's also the current minimum (top of the minimum stack).
If the element being removed is the current minimum, also remove it from the minimum stack. This ensures the minimum stack always reflects the correct minimum value for the remaining elements.
To get the minimum element at any time, simply look at the top of the minimum stack. This gives you the current minimum in constant time, without having to search through the entire main stack.

Code Implementation

class MinStack:

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

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

        # Update the minimum stack with the current minimum value
        if not self.minimum_stack or value <= self.minimum_stack[-1]:
            self.minimum_stack.append(value)

    def pop(self):
        if not self.stack:
            return

        popped_value = self.stack.pop()

        # If popped is current min, pop from minimum stack too
        if popped_value == self.minimum_stack[-1]:
            self.minimum_stack.pop()

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

    def getMin(self):
        # Provides minimum element in stack at O(1) time
        if self.minimum_stack:
            return self.minimum_stack[-1]

Big(O) Analysis

Time Complexity

O(1) – The Min Stack implementation involves operations such as push, pop, top, and getMin. Each of these operations only involves constant time operations like comparing the new element with the current minimum, and adding/removing elements from the top of stacks. These operations do not depend on the number of elements (n) currently in the stack. Therefore, the time complexity for each operation is O(1).

Space Complexity

O(N) – The solution utilizes two stacks: one to store the elements and another to store the minimums at each step. In the worst-case scenario, where the elements are pushed in monotonically decreasing order, every element will also be added to the minimum stack. Thus, both stacks can grow up to the size of the input, N, where N is the number of elements pushed onto the stack. The auxiliary space is therefore proportional to N, making the space complexity O(N).

Edge Cases

Case	How to Handle
Initial stack is empty and getMin is called	Throw an exception or return a specific error value (e.g., Integer.MAX_VALUE or null) to signal no minimum exists.
Large number of push operations causing potential memory overflow	Ensure that underlying data structures (e.g., ArrayList, linked list) have dynamic resizing to accommodate a large number of elements; consider memory limitations during design.
Pushing and popping elements such that the minimum element changes frequently	The auxiliary stack for maintaining minimums ensures O(1) getMin regardless of minimum value fluctuation.
Stack contains Integer.MIN_VALUE and more values are pushed	Handle Integer.MIN_VALUE carefully to avoid underflow when updating the minimum values; consider using long to represent the minimum if necessary.
Stack contains duplicate minimum values	Auxiliary stack should correctly track all occurences or equivalents of the true minimum value.
Calling top on an empty stack	Throw an exception or return a specific error value (e.g., null) to indicate an empty stack.
Sequence of pushes followed by a sequence of pops that empties the stack.	The minimum stack should be correctly updated after each pop and getMin should function as intended upon each call.
Negative numbers being pushed onto the stack	The comparison logic needs to work correctly with negative numbers to accurately track the minimum value.