Design a stack that supports getMin() in O(1) time

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 Last-In-First-Out (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:

1. 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 the minStack.

2. 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 the minStack as well.

3. Top Operation:

   • Return the top element of the main stack.

4. GetMin Operation:

   • Return the top element of the minStack, which is the current minimum.

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 step-by-step example to understand how the MinStack works.

Example Operations

Consider the following sequence of operations:

1. push(5)
2. push(3)
3. push(7)
4. push(2)
5. pop()
6. 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:

1. push(5): stack becomes [5]. Since minStack is empty, we also push 5 onto minStack.
2. push(3): stack becomes [5, 3]. 3 is less than the top of minStack (5), so we push 3 onto minStack.
3. push(7): stack becomes [5, 3, 7]. 7 is greater than the top of minStack (3), so minStack remains unchanged.
4. push(2): stack becomes [5, 3, 7, 2]. 2 is less than the top of minStack (3), so we push 2 onto minStack.
5. pop(): stack becomes [5, 3, 7]. The popped value is 2, which is also the top of minStack. Therefore, we pop 2 from minStack as well.
6. getMin(): Returns 3, which is the current minimum in minStack.

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) takes O(1) time.
• Space Complexity: The space complexity is O(n) where n is the number of elements pushed to the stack. In the worst case, every element could be the new minimum, resulting in the minStack being the same size as the main stack.

Conclusion

The MinStack is a powerful and efficient data structure that supports stack operations while providing constant-time 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.