Min Stack Design in DSA Javascript - Deep Dive

Overview - Min Stack Design

What is it?

A Min Stack is a special kind of stack that, besides the usual push and pop operations, can also return the smallest element in the stack instantly. It works like a normal stack but keeps track of the minimum value at every step. This means you can always ask for the smallest number without searching through the whole stack. It is useful when you need quick access to the minimum value while still using a stack.

Why it matters

Without a Min Stack, finding the smallest element in a stack would require checking every item, which takes time. This slows down programs that need to know the minimum often. Min Stack solves this by remembering the smallest value as you add or remove items, making the process very fast. This helps in real-world tasks like tracking minimum prices, temperatures, or scores efficiently.

Where it fits

Before learning Min Stack, you should understand what a stack is and how it works (push, pop, peek). After mastering Min Stack, you can explore other advanced stack variations like Max Stack or design problems involving multiple stacks or queues.

Mental Model

Core Idea

A Min Stack remembers the smallest value at every step so you can get it instantly without searching.

Think of it like...

Imagine stacking boxes where each box has a note showing the smallest box size in the stack below it. When you add or remove a box, you update the note so you always know the smallest box size on top.

Stack Top
┌─────────┐
│ Value: 5│
│ Min:  2 │
├─────────┤
│ Value: 2│
│ Min:  2 │
├─────────┤
│ Value: 7│
│ Min:  7 │
└─────────┘

Each element stores its value and the minimum value up to that point.

Build-Up - 7 Steps

1

Foundation

Understanding Basic Stack Operations

Concept: Learn how a stack works with push and pop operations.

A stack is like a pile of plates. You can add a plate on top (push) or remove the top plate (pop). The last plate you put on is the first one you take off. This is called Last-In-First-Out (LIFO). For example, pushing 1, then 2, then 3 results in a stack with 3 on top. Popping removes 3 first.

Result

Stack after pushes: 1 -> 2 -> 3 -> null Stack after one pop: 1 -> 2 -> null

Understanding push and pop is essential because Min Stack builds on these operations by adding minimum tracking.

2

Foundation

What is the Minimum Element Problem?

Concept: Recognize the challenge of finding the smallest element in a stack quickly.

If you want to find the smallest number in a stack, you might check every element one by one. This takes time proportional to the stack size. For example, in stack 3 -> 1 -> 4 -> 2, finding the minimum means looking at all four elements each time.

Result

Minimum found by scanning: 1 Time taken: O(n) where n is stack size

Knowing this problem shows why a special stack that tracks minimums is useful for faster access.

3

Intermediate

Tracking Minimum with Extra Stack

🤔Before reading on: do you think we can find the minimum in O(1) time by storing minimums separately? Commit to yes or no.

Concept: Use a second stack to keep track of minimum values at each push.

Alongside the main stack, keep another stack that stores the minimum value so far. When pushing a new value, compare it with the current minimum and push the smaller one onto the min stack. When popping, pop from both stacks. This way, the top of the min stack always shows the current minimum.

Result

Main stack: 5 -> 2 -> 7 Min stack: 5 -> 2 -> 2 Minimum is top of min stack: 2

Using a second stack to track minimums allows constant time retrieval without scanning the main stack.

4

Intermediate

Implementing Min Stack in JavaScript

🤔Before reading on: do you think storing minimums in a separate stack doubles memory usage? Commit to yes or no.

Concept: Write code to push, pop, and get minimum using two stacks.

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); } else { this.minStack.push(this.minStack[this.minStack.length - 1]); } } pop() { this.minStack.pop(); return this.stack.pop(); } top() { return this.stack[this.stack.length - 1]; } getMin() { return this.minStack[this.minStack.length - 1]; } } // Example usage: const minStack = new MinStack(); minStack.push(5); minStack.push(2); minStack.push(7); const min = minStack.getMin(); // 2

Result

minStack.getMin() returns 2 instantly Stack state: 5 -> 2 -> 7 Min stack state: 5 -> 2 -> 2

Implementing with two stacks is straightforward and ensures all operations run in constant time.

5

Intermediate

Optimizing Space by Storing Minimums Conditionally

🤔Before reading on: do you think we must store the minimum for every element? Commit to yes or no.

Concept: Store minimum values only when they change to save memory.

Instead of pushing the current minimum every time, push it only when the new value is smaller or equal. When popping, if the popped value equals the current minimum, pop it from the min stack too. This reduces extra space used by the min stack.

Result

Main stack: 5 -> 2 -> 7 Min stack: 5 -> 2 Minimum is top of min stack: 2

Knowing when to update the min stack saves memory while keeping constant time operations.

6

Advanced

Handling Edge Cases and Empty Stack Operations

🤔Before reading on: do you think calling getMin on an empty stack should return null or throw an error? Commit to your answer.

Concept: Design safe behavior for operations when the stack is empty.

When the stack is empty, pop or getMin operations should handle gracefully. For example, getMin can return null or undefined instead of crashing. Similarly, popping from an empty stack should not cause errors but return undefined or a message. This makes the Min Stack robust in real applications.

Result

Calling getMin on empty stack returns null Popping from empty stack returns undefined

Handling edge cases prevents runtime errors and makes the data structure reliable.

7

Expert

Surprising Internals: Using Single Stack with Encoded Minimums

🤔Before reading on: do you think it's possible to track minimums without a second stack? Commit to yes or no.

Concept: Use clever encoding to store minimums within one stack to save space.

Instead of two stacks, store differences between current value and minimum in one stack. When pushing, if new value is less than current minimum, push a special encoded value and update minimum. When popping, decode to restore previous minimum. This reduces memory but requires careful math and is tricky to implement.

Result

Single stack stores values and encoded minimums Minimum retrieved in O(1) without extra stack

Understanding this technique reveals deep optimization possibilities beyond the common two-stack method.

Under the Hood

The Min Stack keeps track of the minimum element by storing it alongside each pushed value or separately in a parallel stack. When a new element is pushed, it compares with the current minimum and updates accordingly. This ensures that the minimum can be retrieved instantly by looking at the top of the min stack. Internally, this avoids scanning the entire stack by maintaining a history of minimums synchronized with the main stack operations.

Why designed this way?

The design balances time and space efficiency. Using a second stack for minimums keeps operations at constant time, which is critical for performance. Alternatives like scanning the stack for minimum are slower. The single stack encoding method was designed later to optimize space but is more complex. The two-stack approach was chosen for its simplicity and speed in most practical cases.

Main Stack      Min Stack
┌─────────┐    ┌─────────┐
│   7     │    │   7     │
├─────────┤    ├─────────┤
│   2     │    │   2     │
├─────────┤    ├─────────┤
│   5     │    │   2     │
└─────────┘    └─────────┘

Push 7: min stack empty, push 7
Push 2: 2 < 7, push 2
Push 5: 5 > 2, push 2 again
Pop: remove 5 and top min 2
Minimum is top of min stack

Myth Busters - 3 Common Misconceptions

Quick: Does the min stack always have fewer elements than the main stack? Commit to yes or no.

Common Belief: The min stack always has fewer elements than the main stack because it only stores minimums.

Reality: The min stack can have the same number of elements as the main stack if the minimum value repeats or is pushed multiple times.

Why it matters: Assuming fewer elements can lead to wrong memory usage estimates and inefficient implementations.

Quick: Can you get the minimum element by just looking at the top of the main stack? Commit to yes or no.

Common Belief: The top element of the main stack is always the minimum element.

Reality: The top element is just the last pushed value and may not be the minimum. The min stack tracks the minimum separately.

Why it matters: Confusing top with minimum causes incorrect results and bugs in algorithms relying on minimum values.

Quick: Is it always better to use a single stack with encoding for minimums? Commit to yes or no.

Common Belief: Using a single stack with encoded minimums is always the best approach.

Reality: While it saves space, the single stack encoding is complex and error-prone, making the two-stack method preferable in most cases.

Why it matters: Choosing the wrong method can increase bugs and maintenance difficulty in production code.

Expert Zone

1

The min stack must handle duplicate minimum values carefully to avoid losing track when popping.

2

In concurrent environments, atomic operations or locks are needed to maintain consistency of min stack.

3

The single stack encoding method relies on arithmetic overflow-safe operations, which can be tricky in some languages.

When NOT to use

Min Stack is not suitable when you need to find minimums over sliding windows or ranges; data structures like segment trees or balanced BSTs are better. Also, if memory is extremely limited and complexity must be minimal, simpler stacks without minimum tracking may be preferred.

Production Patterns

Min Stack is used in real-time systems to track minimum sensor readings, in financial apps to monitor lowest prices, and in algorithms like monotonic stack problems. It often appears in coding interviews to test understanding of stack and optimization.

Connections

Monotonic Stack

Builds-on

Understanding Min Stack helps grasp monotonic stacks, which maintain order properties to solve range and next greater/smaller element problems efficiently.

Priority Queue

Opposite

While Min Stack gives instant access to minimum in LIFO order, priority queues provide minimum in any order but with more overhead, showing tradeoffs in data structure design.

Real-time Monitoring Systems

Application

Min Stack concepts apply to real-time systems tracking minimum values like temperature or stock prices, demonstrating how data structures solve practical problems.

Common Pitfalls

#1 Not updating the min stack when pushing a new minimum value.

Wrong approach:

push(val) {
this.stack.push(val);
if (this.minStack.length === 0) {
this.minStack.push(val);
}
// Missing else case to push current min again
}

Correct approach:

push(val) {
this.stack.push(val);
if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
this.minStack.push(val);
} else {
this.minStack.push(this.minStack[this.minStack.length - 1]);
}
}

Root cause:

Forgetting to keep min stack synchronized causes getMin to return wrong values.

#2 Popping only from the main stack but not from the min stack.

Wrong approach:

pop() {
return this.stack.pop();
// Missing minStack.pop()
}

Correct approach:

pop() {
this.minStack.pop();
return this.stack.pop();
}

Root cause:

Not popping from min stack breaks the alignment, causing incorrect minimum tracking.

#3 Calling getMin on an empty stack without checks.

Wrong approach:

getMin() {
return this.minStack[this.minStack.length - 1];
// No check for empty minStack
}

Correct approach:

getMin() {
if (this.minStack.length === 0) return null;
return this.minStack[this.minStack.length - 1];
}

Root cause:

Ignoring empty stack cases leads to runtime errors.

Key Takeaways

A Min Stack extends a normal stack by tracking the smallest element at every step for instant retrieval.

Using a second stack to store minimums keeps all operations in constant time, making it efficient.

Optimizations can reduce memory by storing minimums only when they change, but require careful handling.

Edge cases like empty stack operations must be handled to avoid errors in real applications.

Advanced techniques allow minimum tracking with a single stack using encoding, but with added complexity.

Practice

1. What is the main purpose of a Min Stack data structure?

easy

A. To store elements in a queue fashion

B. To sort elements in ascending order

C. To retrieve the minimum element in constant time

D. To reverse the order of elements

Solution

1. Step 1: Understand the Min Stack concept

   A Min Stack is designed to keep track of the minimum element at any time efficiently.

2. Step 2: Identify the main feature

   The key feature is to get the minimum element in constant time, without scanning all elements.

3. Final Answer:

   To retrieve the minimum element in constant time -> Option C

4. Quick Check:

   Min Stack = fast minimum retrieval [OK]

Hint: Min Stack always returns minimum quickly [OK]

Common Mistakes:

• Thinking it sorts elements
• Confusing with queue behavior
• Assuming it reverses elements

2. Which of the following is the correct way to initialize a Min Stack class in JavaScript?

easy

A. class MinStack { constructor() { this.stack = []; this.minStack = []; } }

B. function MinStack() { this.stack = {}; this.minStack = {}; }

C. class MinStack { constructor() { this.stack = null; this.minStack = null; } }

D. var MinStack = () => { this.stack = []; this.minStack = []; }

Solution

1. Step 1: Check class syntax and initialization

   class MinStack { constructor() { this.stack = []; this.minStack = []; } } correctly uses ES6 class syntax with constructor initializing two arrays.

2. Step 2: Identify incorrect options

   The function constructor uses object literals {} instead of arrays. Initializing stacks to null is incorrect. Arrow functions cannot be used for class constructors.

3. Final Answer:

   class MinStack { constructor() { this.stack = []; this.minStack = []; } } -> Option A

4. Quick Check:

   Correct class and array initialization = class MinStack { constructor() { this.stack = []; this.minStack = []; } } [OK]

Hint: Use ES6 class with arrays for stacks [OK]

Common Mistakes:

• Using object literals instead of arrays
• Initializing stacks as null
• Using arrow functions for classes

3. What will be the output of the following code?

const minStack = new MinStack();
minStack.push(3);
minStack.push(5);
minStack.push(2);
minStack.push(1);
minStack.pop();
console.log(minStack.getMin());

Assuming MinStack is implemented correctly with push, pop, and getMin methods.

medium

A. 2

B. 5

C. 3

D. 1

Solution

1. Step 1: Trace the push operations

   Push 3, 5, 2, 1 in order. Stack: [3,5,2,1]. Minimum is 1.

2. Step 2: Pop the last element and check minimum

   Pop removes 1. Stack becomes [3,5,2]. Minimum now is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   After pop, min = 2 [OK]

Hint: Pop removes min, next min updates [OK]

Common Mistakes:

• Forgetting to update min after pop
• Assuming min stays same after pop
• Confusing stack order

4. Identify the bug in this pop method of a Min Stack:

pop() {
  if (this.stack.length === 0) return null;
  const popped = this.stack.pop();
  if (popped === this.minStack[this.minStack.length - 1]) {
    this.minStack.pop();
  }
  return popped;
}

medium

A. It returns popped value instead of void

B. It does not check if stack is empty before popping

C. It compares popped value with minStack top incorrectly

D. It does not update minStack when popping minimum

Solution

1. Step 1: Analyze pop method behavior

   The method pops from stack and conditionally pops from minStack. It returns the popped value.

2. Step 2: Check expected pop return type in Min Stack

   Usually, pop in Min Stack returns void (no value). Returning popped value may cause misuse or confusion.

3. Final Answer:

   It does not check if stack is empty before popping -> Option B

4. Quick Check:

   Pop should check for empty stack before popping [OK]

Hint: Pop should check empty stack before popping [OK]

Common Mistakes:

• Returning popped value instead of void
• Not checking empty stack before pop
• Incorrect minStack update logic

5. You want to design a Min Stack that supports push, pop, top, and getMin all in constant time. Which approach below is the best to achieve this?

hard

A. Use a linked list and traverse it to find minimum on getMin

B. Use one stack and scan all elements to find min when needed

C. Use a queue to store elements and sort it on every push

D. Use two stacks: one for all elements, one for current minimums

Solution

1. Step 1: Understand time complexity requirements

   All operations must be constant time, so scanning or sorting on each operation is not allowed.

2. Step 2: Evaluate each approach

   Scanning all elements to find the minimum, traversing a linked list, or sorting on every push all take more than constant time. Using two stacks--one for all elements, one for current minimums--ensures constant time for all operations.

3. Final Answer:

   Use two stacks: one for all elements, one for current minimums -> Option D

4. Quick Check:

   Two stacks = constant time min retrieval [OK]

Hint: Two stacks track elements and minimum separately [OK]

Common Mistakes:

• Using scanning or sorting which is slow
• Confusing queue with stack behavior
• Ignoring constant time requirement