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

Min Stack

Understand how to implement a custom Min Stack data structure that supports push, pop, and retrieving the minimum element in constant time. This lesson guides you through building methods to maintain efficient operations, essential for solving complex coding interview problems involving stacks.

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