Stack with Minimum Element in JavaScript

Implement a stack data structure in JavaScript that supports all standard stack operations (push, pop, peek) and additionally allows retrieving the minimum element currently in the stack in O(1) time complexity. This is a common interview question that tests your understanding of data structures and how to optimize operations.

Problem Description

You need to design and implement a JavaScript class, let's call it MinStack. This class should behave like a regular stack but with an added getMin() method.

Key Requirements:

1. push(val): Pushes an element val onto the stack.
2. pop(): Removes and returns the element at the top of the stack.
3. peek(): Returns the element at the top of the stack without removing it.
4. getMin(): Returns the current minimum element in the stack. This operation must have a time complexity of O(1).

Expected Behavior:

• When an element is pushed, the stack should update its internal state to correctly track the minimum element.
• When an element is popped, the minimum element tracking should also be updated.
• getMin() should always return the smallest value currently present in the stack.
• If the stack is empty, pop() and peek() should ideally return undefined or throw an error (specify your chosen behavior). For getMin(), it should also return undefined or throw an error.

Edge Cases to Consider:

• Pushing duplicate minimum values.
• Popping the current minimum value.
• An empty stack.

Examples

Example 1:

Input:
const minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // Output: -3
minStack.pop();
minStack.peek();   // Output: 0
minStack.getMin(); // Output: -2

Output:

• minStack.getMin() returns -3.
• minStack.peek() returns 0.
• minStack.getMin() returns -2.

Explanation:

1. push(-2): Stack: [-2], Min: -2
2. push(0): Stack: [-2, 0], Min: -2
3. push(-3): Stack: [-2, 0, -3], Min: -3
4. getMin(): Returns -3.
5. pop(): Removes -3. Stack: [-2, 0], Min: -2 (old min is still valid)
6. peek(): Returns 0.
7. getMin(): Returns -2.

Example 2:

Input:
const minStack = new MinStack();
minStack.push(5);
minStack.push(2);
minStack.push(5);
minStack.push(1);
minStack.getMin(); // Output: 1
minStack.pop();    // removes 1
minStack.getMin(); // Output: 2
minStack.pop();    // removes 5
minStack.getMin(); // Output: 2
minStack.pop();    // removes 2
minStack.getMin(); // Output: 5

Output:

• minStack.getMin() returns 1.
• minStack.getMin() returns 2.
• minStack.getMin() returns 2.
• minStack.getMin() returns 5.

Explanation:

1. push(5): Stack: [5], Min: 5
2. push(2): Stack: [5, 2], Min: 2
3. push(5): Stack: [5, 2, 5], Min: 2
4. push(1): Stack: [5, 2, 5, 1], Min: 1
5. getMin(): Returns 1.
6. pop(): Removes 1. Stack: [5, 2, 5]. The next minimum is 2.
7. getMin(): Returns 2.
8. pop(): Removes 5. Stack: [5, 2]. The next minimum is 2.
9. getMin(): Returns 2.
10. pop(): Removes 2. Stack: [5]. The next minimum is 5.
11. getMin(): Returns 5.

Example 3: Empty Stack

Input:
const minStack = new MinStack();
minStack.getMin(); // Output: undefined (or error)
minStack.pop();    // Output: undefined (or error)

Output:

• minStack.getMin() returns undefined.
• minStack.pop() returns undefined.

Constraints

• The values pushed onto the stack will be integers.
• You may assume that pop() and peek() are called only when there is at least one element in the stack (if you choose not to handle empty stack explicitly by returning undefined).
• The getMin() operation must be O(1) time complexity.
• Other operations (push, pop, peek) can be O(1) or O(N) where N is the number of elements in the stack, but O(1) is preferred for an optimal solution.

Notes

• Think about how to store additional information with each element pushed onto the stack to efficiently track the minimum.
• Consider using an auxiliary data structure or augmenting the elements stored in the primary stack.
• Be mindful of the time complexity for getMin().