In this blog post, we’ll explore the MinStack
data structure in JavaScript, covering its design, implementation, and how it works under the hood. We’ll also include visualizations to help you better understand how this data structure maintains the minimum value while performing typical stack operations.
Overview of the MinStack Problem
A stack is a data structure that follows the LastInFirstOut (LIFO) principle. In a typical stack, you can perform the following operations:
 Push: Add an element to the top of the stack.
 Pop: Remove the element from the top of the stack.
 Top: Retrieve the element at the top of the stack.
However, the MinStack
extends the standard stack with an additional operation:
 GetMin: Retrieve the minimum element from the stack in constant time (
O(1)
).
Designing the MinStack
To achieve O(1)
time complexity for getMin()
, we need to maintain an auxiliary stack (minStack
) that stores the minimum value up to the current point in the primary stack.
Here’s how the operations are handled:

Push Operation:
 Push the value to the main stack.
 If the value is smaller than or equal to the current minimum value (or if the
minStack
is empty), also push it onto theminStack
.

Pop Operation:
 Pop the value from the main stack.
 If the popped value is the same as the top of the
minStack
, pop it from theminStack
as well.

Top Operation:
 Return the top element of the main stack.

GetMin Operation:
 Return the top element of the
minStack
, which is the current minimum.
 Return the top element of the
Implementation in JavaScript
Below is the JavaScript implementation of the MinStack
:
class MinStack {
constructor() {
this.stack = [];
this.minStack = [];
}
push(x) {
this.stack.push(x);
if (this.minStack.length === 0  x <= this.minStack[this.minStack.length  1]) {
this.minStack.push(x);
}
}
pop() {
const val = this.stack.pop();
if (val === this.minStack[this.minStack.length  1]) {
this.minStack.pop();
}
}
top() {
return this.stack[this.stack.length  1];
}
getMin() {
return this.minStack[this.minStack.length  1];
}
}
Visualization of MinStack Operations
Let’s go through a stepbystep example to understand how the MinStack
works.
Example Operations
Consider the following sequence of operations:
push(5)
push(3)
push(7)
push(2)
pop()
getMin()
Let’s visualize the state of the stack
and minStack
after each operation.
Operation  Main Stack (stack ) 
Min Stack (minStack ) 
getMin() 

push(5)  [5]  [5]  5 
push(3)  [5, 3]  [5, 3]  3 
push(7)  [5, 3, 7]  [5, 3]  3 
push(2)  [5, 3, 7, 2]  [5, 3, 2]  2 
pop()  [5, 3, 7]  [5, 3]  3 
getMin()  [5, 3, 7]  [5, 3]  3 
Explanation of Each Step:
 push(5):
stack
becomes[5]
. SinceminStack
is empty, we also push5
ontominStack
.  push(3):
stack
becomes[5, 3]
.3
is less than the top ofminStack
(5
), so we push3
ontominStack
.  push(7):
stack
becomes[5, 3, 7]
.7
is greater than the top ofminStack
(3
), sominStack
remains unchanged.  push(2):
stack
becomes[5, 3, 7, 2]
.2
is less than the top ofminStack
(3
), so we push2
ontominStack
.  pop():
stack
becomes[5, 3, 7]
. The popped value is2
, which is also the top ofminStack
. Therefore, we pop2
fromminStack
as well.  getMin(): Returns
3
, which is the current minimum inminStack
.
Why Does This Work?
The trick lies in maintaining two stacks:
 The main stack (
stack
) holds all the pushed elements.  The minimum stack (
minStack
) maintains a history of minimum values in descending order of when they were pushed.
Whenever we push a new element that is less than or equal to the current minimum, it also gets pushed onto the minStack
. When we pop an element, if it is the current minimum (i.e., the top of the minStack
), we pop from both stacks. This ensures that minStack
always contains the current minimum at the top.
Complexity Analysis
 Time Complexity: Each operation (
push
,pop
,top
,getMin
) takesO(1)
time.  Space Complexity: The space complexity is
O(n)
wheren
is the number of elements pushed to the stack. In the worst case, every element could be the new minimum, resulting in theminStack
being the same size as the mainstack
.
Conclusion
The MinStack
is a powerful and efficient data structure that supports stack operations while providing constanttime access to the minimum element. By maintaining an auxiliary stack (minStack
), we can optimize the getMin
operation to O(1)
without compromising the efficiency of other stack operations.
Optimize Space Usage
Instead of storing duplicate elements in the minStack
, store tuples or pairs that count how many times the minimum element is repeated.