Implement a Stack With Minimum
Read at your own pace. Code execution, quizzes, progress tracking, and the AI tutor are available in the interactive view with JavaScript enabled.
Description
Recall that a stack is an abstract data type modeling a collection of elements. Its primary operations are push (which adds an element to the top of the stack) and pop (which removes the most newest element).
Traditionally, a stack can easily be implemented in many dynamic languages using an array (and its built-in methods).
const stack = [];
stack.push(5);
stack.push(6);
stack.push(7);
stack.pop();
// 7
stack.pop();
// 6
stack = []
stack.append(5)
stack.append(6)
stack.append(7)
print(stack.pop())
# 7
print(stack.pop())
# 6
Stack<Integer> stack = new Stack<>();
stack.push(5);
stack.push(6);
stack.push(7);
System.out.println(stack.pop());
// Output: 7
System.out.println(stack.pop());
// Output: 6
std::stack<int> stack;
stack.push(5);
stack.push(6);
stack.push(7);
std::cout << stack.top(); stack.pop(); // Prints 7
// Output: 7
std::cout << stack.top(); stack.pop(); // Prints 6
// Output: 6
Stack<int> stack = new Stack<int>();
stack.Push(5);
stack.Push(6);
stack.Push(7);
Console.WriteLine(stack.Pop());
// Output: 7
Console.WriteLine(stack.Pop());
// Output: 6
stack := []int{}
stack = append(stack, 5)
stack = append(stack, 6)
stack = append(stack, 7)
fmt.Println(stack[len(stack)-1]) // Prints 7.
stack = stack[:len(stack)-1] // pops the top(the last) element
// Output: 7
fmt.Println(stack[len(stack)-1]) // Prints 6.
stack = stack[:len(stack)-1] // pops the top(the last) element
// Output: 6
However, let's say we wanted to implement a stack with the following interface, requiring the following methods to be defined. The most important being the last one, min() - a method that lets us obtain the minimum element at any given time.
push(val) - add an element on to the top of the stack.
pop(val) - remove the element at the top of the stack and return it.
peek(val) - see the element at the top of the stack without removing it.
min() - get minimum element in stack.
How would you do it, and can you implement it via a MinStack class? The class should have the following methods. Work off this skeleton:
class MinStack {
constructor() {
}
push(val) {
}
pop() {
}
peek() {
}
min() {
}
}
Can you do call min() and retrieve it in O(1) time?
Constraints
- Total number of operations in the stack <=
100000 - The values will be in the range
-1000000000and1000000000 - Expected time complexity : O(1)
- Expected space complexity : O(n)
```js
class MinStack {
constructor() {
}
push(val) {
}
pop() {
}
peek() {
}
min() {
}
}
```
```java
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack = new Stack<Integer>();
minStack = new Stack<Integer>();
}
public void push(int val) {
stack.push(val);
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
if (!stack.isEmpty()) {
int value = stack.pop();
if(value == minStack.peek()){
minStack.pop();
}
}
}
public int peek() {
return stack.peek();
}
public int min() {
return minStack.peek();
}
}
public class Main {
public static void main(String[] args) {
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();
minStack.pop();
minStack.peek();
minStack.min();
}
}
```
```javascript
class MinStack {
constructor() {
this.stack = [];
this.minStack = [];
}
push(val) {
this.stack.push(val);
if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
this.minStack.push(val);
}
}
pop() {
const val = this.stack.pop();
if (val === this.minStack[this.minStack.length - 1]) {
this.minStack.pop();
}
}
peek() {
return this.stack[this.stack.length - 1];
}
min() {
return this.minStack[this.minStack.length - 1];
}
};
```
```python
class MinStack:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, val):
self.stack.append(val)
if len(self.minStack) == 0 or val <= self.minStack[-1]:
self.minStack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.minStack[-1]:
self.minStack.pop()
def peek(self):
return self.stack[-1]
def min(self):
return self.minStack[-1]
minStack = MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
minStack.min()
minStack.pop()
minStack.peek()
minStack.min()
```
```cpp
#include <stack>
class MinStack {
std::stack<int> stack, minStack;
public:
MinStack() = default;
void push(int val) {
stack.push(val);
if (minStack.empty() || val <= minStack.top()) {
minStack.push(val);
}
}
void pop() {
if(stack.top() == minStack.top()) minStack.pop();
stack.pop();
}
int peek() {
return stack.top();
}
int min() {
return minStack.top();
}
};
int main() {
MinStack minStack;
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();
minStack.pop();
minStack.peek();
minStack.min();
}
```
```csharp
public class MinStack
{
private Stack<int> stack;
private Stack<int> minStack;
public MinStack()
{
stack = new Stack<int>();
minStack = new Stack<int>();
}
public void Push(int val)
{
stack.Push(val);
if (!minStack.Any() || val <= minStack.Peek())
{
minStack.Push(val);
}
}
public void Pop()
{
int value = stack.Pop();
if (value == minStack.Peek())
{
minStack.Pop();
}
}
public int Peek()
{
return stack.Peek();
}
public int Min()
{
return minStack.Peek();
}
}
public class Program
{
public static void Main(string[] args)
{
MinStack minStack = new MinStack();
minStack.Push(-2);
minStack.Push(0);
minStack.Push(-3);
minStack.Min();
minStack.Pop();
minStack.Peek();
minStack.Min();
}
}
```
```go
package main
import "fmt"
type MinStack struct {
stack []int
minStack []int
}
func Constructor() MinStack {
return MinStack{}
}
func (this *MinStack) Push(val int) {
this.stack = append(this.stack, val)
if len(this.minStack) == 0 || val <= this.minStack[len(this.minStack)-1] {
this.minStack = append(this.minStack, val)
}
}
func (this *MinStack) Pop() {
val := this.stack[len(this.stack)-1]
this.stack = this.stack[:len(this.stack)-1]
if val == this.minStack[len(this.minStack)-1] {
this.minStack = this.minStack[:len(this.minStack)-1]
}
}
func (this *MinStack) Peek() int {
return this.stack[len(this.stack)-1]
}
func (this *MinStack) Min() int {
return this.minStack[len(this.minStack)-1]
}
func main() {
minStack := Constructor()
minStack.Push(-2)
minStack.Push(0)
minStack.Push(-3)
fmt.Println(minStack.Min())
minStack.Pop()
fmt.Println(minStack.Peek())
fmt.Println(minStack.Min())
}
```CONTINUE WITH ALGODAILY PREMIUM
Keep going with the complete tutorial.
Unlock the remaining explanations and exercises, alongside the full learning library.
Explore Premium →