155. Min Stack

MediumStackDesign
Leetcode Link

Problem Description

The problem requires designing a stack data structure with not only the standard operations - push, pop, and top - but also the ability to retrieve the minimum element present in the stack at any time, all in constant time O(1). This is quite challenging because the standard stack data structure does not keep track of the minimum element, and searching for the minimum element typically requires O(n) time where n is the number of elements in the stack.

To summarize, MinStack class should support these operations:

  • MinStack() constructor that initializes the stack.
  • push(int val) that adds an element to the stack.
  • pop() that removes the element at the top of the stack.
  • top() that retrieves the element at the top of the stack without removing it.
  • getMin() that retrieves the minimum element present in the stack.

Each of these operations must be done in O(1) time complexity.

Intuition

To maintain the minimum element information in constant time, we need a strategy that keeps track of the minimum at each state of the stack. The solution uses two stacks:

  • The first stack stk1 behaves like a normal stack, holding all the elements.
  • The second stack stk2 keeps track of minimum elements. Each element in stk2 corresponds to the minimum element of stk1 up to that point.

With each push, we insert the value into stk1 and also update the stk2 with the minimum of the new value and the current minimum, which is the top element of stk2.

Upon pop, we simply remove the top elements from both stk1 and stk2. Given stk2 is always in sync with stk1 but only storing minimums, it ensures that stk2's top always represents the current minimum of stk1.

top is straightforward as we return the top element of stk1 whereas getMin returns the top element of stk2.

This design allows for the stack to operate as normal while having a supporting structure, stk2, that efficiently tracks the minimum element. Thus, all the required operations run in constant time, fulfilling the problem constraints.

Learn more about Stack patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Solution Approach

The solution involves using two stacks to keep track of the minimum element in conjunction with the main stack operations. Here is how the solution is implemented for each function of the MinStack class:

__init__(self)

  • Initialize two empty lists, self.stk1 and self.stk2. The first list self.stk1 is used as the primary stack to store the values. The second list self.stk2 serves as an auxiliary stack to store the minimum values seen so far.
  • Append inf (infinity) to self.stk2 to handle the edge case when the first element is pushed onto the stack.

push(self, val: int)

  • Append the value val to the primary stack self.stk1.
  • To maintain the minimum in self.stk2, append the minimum of the new value val and the last element in self.stk2 (which is the current minimum) to self.stk2.

pop(self)

  • Pop the top element from self.stk1, which is the standard stack operation.
  • Similarly, pop the top element from self.stk2. This ensures that after the pop operation, the minimum value is updated correspondingly in self.stk2.

top(self)

  • Return the top element of self.stk1 by accessing the last element in the list self.stk1[-1] without removing it. This is the standard 'peek' operation in stack.

getMin(self)

  • Return the top element of self.stk2 by accessing the last element in the list self.stk2[-1]. Since self.stk2 is maintained in a way that its top always contains the minimum element of the stack, this gives us the current minimum in constant time.

In conclusion, the algorithm leverages an auxiliary stack self.stk2 that mirrors the push and pop operations of the primary stack self.stk1. It cleverly keeps track of the minimum element at each level of the stack as elements are added and removed, which allows for constant time retrieval of the minimum element. This elegant solution satisfies the constraints of the problem statement and ensures that all operations - push, pop, top, and getMin — remain constant time O(1) operations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

  1. Construct a MinStack. Initially, both stk1 and stk2 are empty:

    1stk1: []
2stk2: [inf]

    inf in stk2 is used as a placeholder to simplify the push operation even when the stack is empty.

  2. Push the value 5 onto the stack.

    1push(5)

    stk1 now holds: [5] stk2 updates its minimum value by comparing the current minimum (inf) and 5, choosing the smaller one: [inf, 5]

  3. Push the value 3 onto the stack.

    1push(3)

    stk1 now holds: [5, 3] stk2 updates: [inf, 5, 3] as 3 is the new minimum.

  4. Push the value 7 onto the stack.

    1push(7)

    stk1 now holds: [5, 3, 7] stk2 updates by comparing 3 (current minimum in stk2) and 7, which results in: [inf, 5, 3, 3] (since 3 is smaller).

  5. Retrieve the current minimum.

    1getMin()

    The top of stk2 gives us the minimum: 3.

  6. Pop the top element off the stack.

    1pop()

    After popping, stk1 holds: [5, 3] And stk2 synchronously pops as well to maintain the minimum: [inf, 5, 3].

  7. Retrieve the new current minimum.

    1getMin()

    With the last 7 removed, the new top of stk2 and thus the current minimum is now: 3.

  8. Retrieve the top element.

    1top()

    The top of stk1 gives us the last pushed value which is not removed yet: 3.

By following the above steps for each operation, it is demonstrated that the auxiliary stack stk2 accurately keeps track of the minimum elements for the primary stack stk1 at each point of operation, ensuring that getMin() can always retrieve the current minimum in constant time, O(1).

Solution Implementation

1class MinStack:
2    def __init__(self):
3        # Initialize two stacks; one to hold the actual stack values, 
4        # and the other to keep track of the minimum value at any given point.
5        self.stack = []
6        self.min_stack = [float('inf')]  # Initialize with infinity to handle edge case for the first element pushed
7
8    def push(self, val: int) -> None:
9        # Add the value to the main stack
10        self.stack.append(val)
11        # Add the minimum value to the min_stack which is the minimum of the new value and the current minimum
12        self.min_stack.append(min(val, self.min_stack[-1]))
13
14    def pop(self) -> None:
15        # Remove the top value from both main stack and min_stack
16        self.stack.pop()
17        self.min_stack.pop()
18
19    def top(self) -> int:
20        # Return the top value of the main stack
21        return self.stack[-1]
22
23    def get_min(self) -> int:
24        # Return the current minimum value which is the top value of the min_stack
25        return self.min_stack[-1]
26
27# Example of how the MinStack class can be used:
28# min_stack = MinStack()
29# min_stack.push(-2)
30# min_stack.push(0)
31# min_stack.push(-3)
32# print(min_stack.get_min())  # returns -3
33# min_stack.pop()
34# print(min_stack.top())      # returns 0
35# print(min_stack.get_min())  # returns -2
36
1class MinStack {
2    // stk1 keeps track of all the elements in the stack.
3    private Deque<Integer> stack = new ArrayDeque<>();
4  
5    // minValuesStack keeps track of the minimum values at each state of the stack.
6    private Deque<Integer> minValuesStack = new ArrayDeque<>();
7
8    // Constructor initializes the minValuesStack with the maximum value an integer can hold.
9    public MinStack() {
10        minValuesStack.push(Integer.MAX_VALUE);
11    }
12
13    // Method to push an element onto the stack. Updates the minimum value as well.
14    public void push(int val) {
15        // Push the value onto the stack.
16        stack.push(val);
17        // Push the smaller between the current value and the current minimum onto the minValuesStack.
18        minValuesStack.push(Math.min(val, minValuesStack.peek()));
19    }
20
21    // Method to remove the top element from the stack. Also updates the minimum value.
22    public void pop() {
23        // Remove the top element of the stack.
24        stack.pop();
25        // Remove the top element of the minValuesStack, which corresponds to the minimum at that state.
26        minValuesStack.pop();
27    }
28
29    // Method to retrieve the top element of the stack without removing it.
30    public int top() {
31        // Peek the top element of the stack.
32        return stack.peek();
33    }
34
35    // Method to get the current minimum value in the stack.
36    public int getMin() {
37        // Peek the top element of the minValuesStack, which is the current minimum.
38        return minValuesStack.peek();
39    }
40}
41
1#include <stack>
2#include <climits> // needed for INT_MAX
3using namespace std;
4
5class MinStack {
6public:
7    // Constructor initializes the auxiliary stack with the maximum integer value.
8    MinStack() {
9        minValuesStack.push(INT_MAX);
10    }
11
12    // Pushes a value onto the stack and updates the minimum value stack.
13    void push(int val) {
14        mainStack.push(val);
15        // Push the current minimum value onto the auxiliary stack.
16        // Compares the new value with the current top of the minValuesStack.
17        minValuesStack.push(std::min(val, minValuesStack.top()));
18    }
19
20    // Pops the top element from both the main stack and the minimum value stack.
21    void pop() {
22        mainStack.pop();
23        minValuesStack.pop();
24    }
25
26    // Retrieves the top element of the main stack.
27    int top() {
28        return mainStack.top();
29    }
30
31    // Retrieves the current minimum value from the auxiliary stack.
32    int getMin() {
33        return minValuesStack.top();
34    }
35
36private:
37    // Main stack to store the elements.
38    stack<int> mainStack;
39    // Auxiliary stack to store the minimum values.
40    stack<int> minValuesStack;
41};
42
43/**
44 * The following comments illustrate how a MinStack object is used:
45 * MinStack* obj = new MinStack();
46 * obj->push(val);
47 * obj->pop();
48 * int param_3 = obj->top();
49 * int param_4 = obj->getMin();
50 */
51
1let stack: number[] = []; // This is the primary stack for storing numbers.
2let minStack: number[] = [Infinity]; // This stack keeps track of the minimum values.
3
4/**
5 * Pushes a number onto the stack and updates the minStack appropriately.
6 * @param {number} val - The value to be pushed onto the stack.
7 */
8function push(val: number): void {
9    stack.push(val);
10    minStack.push(Math.min(val, minStack[minStack.length - 1]));
11}
12
13/**
14 * Removes the element on top of the stack and also updates the minStack.
15 */
16function pop(): void {
17    stack.pop();
18    minStack.pop();
19}
20
21/**
22 * Retrieves the element on top of the stack.
23 * @return {number} The top element of the stack.
24 */
25function top(): number {
26    return stack[stack.length - 1];
27}
28
29/**
30 * Retrieves the minimum element from the stack.
31 * @return {number} The current minimum value in the stack.
32 */
33function getMin(): number {
34    return minStack[minStack.length - 1];
35}
36
Not Sure What to Study? Take the 2-min Quiz：

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Time and Space Complexity

The provided Python code defines a class MinStack which implements a stack that, in addition to the typical push and pop operations, can retrieve the smallest element in the stack in constant time.

Time Complexity:

  • __init__: Initializing the MinStack involves setting up two lists (stacks), which is an O(1) operation.
  • push: This method appends a new element to the stk1 and computes the minimum with the last element of stk2 to append to stk2. Both operations are O(1) since appending to a list in Python and retrieving the last element have constant time complexity.
  • pop: Here, we pop from both stk1 and stk2, which are O(1) operations since popping from the end of a list in Python has constant time complexity.
  • top: This method simply returns the last element of stk1, which is an O(1) operation.
  • getMin: Returning the last element of stk2, which is the current minimum, is also an O(1) operation.

Overall, all of the operations of the MinStack class run in constant time, so we have O(1) time complexity for push, pop, top, and getMin methods.

Space Complexity:

  • The space complexity of the MinStack class is mainly due to the space used by the two stacks stk1 and stk2. Assuming n is the number of elements pushed into the stack:
    • stk1 grows linearly with the number of elements pushed, so it has a space complexity of O(n).
    • stk2 also grows with each push operation. Even though it's used to keep the minimum value at each state, it does in pair with the stk1, so its size also corresponds to the number of elements pushed, which makes it O(n) as well.

Therefore, the overall space complexity of the MinStack class is O(n) where n is the number of elements in the stack.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How many ways can you arrange the three letters A, B and C?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫