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

Min Stack

Explore how to create a custom Min Stack data structure that supports push, pop, and minimum retrieval operations all in O(1) time. This lesson helps you understand the design and implementation needed to optimize stack operations for coding interviews.

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 min_stack.py in the following coding playground. You will need the provided supporting code to implement your solution.

Python
usercode > min_stack.py
from stack import MainStack
class MinStack:
    # Initialize min and main stack here
    def __init__(self):
        # Write your code here
        pass
    # Remove and returns value from the stack
    def pop(self):
        # Write your code here
        pass
    # Pushes values into the stack
    def push(self, value):
        # Write your code here
        pass
    # Returns minimum value from stack
    def min_number(self):
        # Write your code here
        pass
Min Stack