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

Min Stack

Explore how to design a Min Stack that allows pushing, popping, and retrieving the minimum value in constant time. This lesson guides you in implementing all operations with O(1) complexity, mastering a key custom data structure useful in coding interviews and real-world problems.

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

Java
usercode > MinStack.java
class MinStack {
	// constructor
	public MinStack() {
		// Write your code here
	}
	
	// Pop() removes and returns value from minStack
	public int pop() {
		// Replace this placeholder return statement with your code
		return -1;
	}
	
	// Pushes values into MinStack
	public void push(Integer value) {
		// Write your code here
	}
	// returns minimum value in O(1)
	public int minNumber() {
		// Replace this placeholder return statement with your code
		return -1;
	}
}
Min Stack