Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C++

Min Stack

Explore how to design a Min Stack that efficiently supports push, pop, and minimum retrieval operations in O(1) time. This lesson helps you deepen your knowledge of custom data structures and apply these techniques to coding interview problems involving optimized stack operations.

We'll cover the following...

Statement

Design a custom stack class, Min Stack, allowing us to push, pop, and retrieve the minimum value in constant time. Implement the following methods for Min Stack:

  • Constructor: This initializes the Min Stack object.

  • Pop(): This removes and returns from the stack the value that was most recently pushed onto it.

  • Push(): This pushes the provided value onto the stack.

  • Min Number(): This returns the minimum value in the stack in O(1)O(1) time.

Note: The time complexity of all the methods above should be O(1)O(1).

Constraints:

  • −104≤-10^{4} \leq value ≤104\leq 10^{4}

  • The Pop() and Min Number() methods will always be called on non-empty stacks.

  • At most, 10310^3 calls will be made to Push(), Pop(), and Min Number().

Examples

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Min Stack

1.

What is the correct output of Min Number() after four Pop() calls are made to the following stack?

stack = [3, 6, 2, 9, 0, 2, 5, -4, 12, -9, 6]

The top element of this stack is 6.

A.

-4

B.

0

C.

-9

D.

3

1 / 3

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Note: These building blocks relate to the scenario of pushing, popping, and retrieving the minimum value from the stack.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4

Try it yourself

Implement your solution in the following coding playground.

C++
usercode > MinStack.cpp
#include <stack>
#include <iostream>
class MinStack {
    public: 
    
        // removes and returns value from stack
        int pop(){
            // Replace this placeholder return statement with your code
            return -1;
        }
        // pushes value into the stack
        void push(int value){
            
            // Write your code here
        }
        // returns maximum value in O(1)
        int minNumber(){
            // Replace this placeholder return statement with your code
            return -1;
        }
};
Min Stack