Search⌘ K
AI Features

Min Stack

Min Stack supports pushing and removing values while returning the current minimum, with every operation required to run in constant time.

Statement

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

  • NewMinStack(): 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.go in the following coding playground. You will need the provided supporting code to implement your solution.

Go
usercode > min_stack.go
package main
// MinStack declaration
type MinStack struct {
// write your code here
}
func NewMinStack() *MinStack {
// Replace this placeholder return statement with your code
return new(MinStack)
}
// Pop removes and returns value from stack
func (m *MinStack) Pop() int {
// Replace this placeholder return statement with your code
return -1
}
// Push pushes value into the stack
func (m *MinStack) Push(value int) {
// write your code here
}
// MinNumber returns minimum value in O(1)
func (m *MinStack) MinNumber() int {
// Replace this placeholder return statement with your code
return -1
}
Min Stack