Min Stack Design in DSA Typescript - Deep Dive

Overview - Min Stack Design

What is it?

A Min Stack is a special kind of stack that, in addition to normal stack operations like push and pop, can also return the smallest element in the stack instantly. It keeps track of the minimum value at every step without searching through all elements. This means you can always get the minimum value in constant time, even after many pushes and pops.

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 quick access to minimum values, like in games, financial apps, or real-time systems. Min Stack solves this by remembering the minimum as you go, making programs faster and more efficient.

Where it fits

Before learning Min Stack, you should understand basic stacks and how push/pop operations work. After mastering Min Stack, you can explore other advanced stack variations like Max Stack or design problems involving queues and heaps.

Mental Model

Core Idea

A Min Stack remembers the smallest value at every step so it can tell you the minimum 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 just look at the top note to know the smallest size so far.

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

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

Build-Up - 7 Steps

1

Foundation

Basic Stack Operations Review

Concept: Understand how a normal stack works with push, pop, and top operations.

A stack is like a pile of plates. You can add a plate on top (push), remove the top plate (pop), or look at the top plate without removing it (top). These operations follow Last-In-First-Out (LIFO) order.

Result

You can add and remove elements only from the top, and see the last added element instantly.

Knowing how a stack works is essential because Min Stack builds on these basic operations and adds minimum tracking.

2

Foundation

Why Finding Minimum is Slow in Normal Stack

Concept: Finding the smallest element in a normal stack requires checking all elements.

If you want the smallest value in a normal stack, you must look at every element because the stack only remembers the top. This takes time proportional to the number of elements (linear time).

Result

Minimum retrieval is slow and inefficient in large stacks.

Understanding this limitation motivates the need for a Min Stack that can do better.

3

Intermediate

Storing Minimum with Each Element

🤔Before reading on: do you think storing the minimum only once at the bottom is enough to track minimum after pops? Commit to yes or no.

Concept: Each element in the stack stores both its value and the minimum value up to that point.

When pushing a new value, compare it with the current minimum. Store the smaller one alongside the value. This way, every element knows the minimum below it. When popping, the new top's stored minimum is the current minimum.

Result

Minimum retrieval becomes instant by looking at the top element's stored minimum.

Knowing minimum at every step avoids searching and keeps minimum retrieval constant time.

4

Intermediate

Implementing Min Stack with Two Stacks

🤔Before reading on: do you think using two stacks (one for values, one for minimums) wastes space or is efficient? Commit to your answer.

Concept: Use one stack for values and another to track minimums separately.

Push values normally. For the min stack, push the new value if it is smaller or equal to the current min. When popping, pop from both stacks if the popped value equals the min stack's top. This keeps minimums synced.

Result

Minimum retrieval is O(1), and space is used efficiently by only storing minimums when they change.

Separating concerns into two stacks simplifies logic and keeps minimum tracking clean.

5

Intermediate

Handling Edge Cases in Min Stack

🤔Before reading on: do you think popping from an empty stack should throw an error or return a special value? Commit to your answer.

Concept: Properly handle empty stack cases and equal minimum values.

Check if the stack is empty before popping or getting minimum to avoid errors. When pushing values equal to current minimum, push them onto min stack too to keep counts correct.

Result

Min Stack behaves safely and correctly even with duplicates and empty states.

Handling edge cases prevents bugs and crashes in real applications.

6

Advanced

Optimizing Space with Single Stack Storage

🤔Before reading on: do you think it's possible to store minimum info without a separate stack? Commit to yes or no.

Concept: Store minimum information cleverly within a single stack using value encoding.

Instead of two stacks, store differences or encoded values that let you recover the minimum on the fly. For example, push a special value when the new minimum is found and update minimum accordingly.

Result

Space usage is reduced while still retrieving minimum in constant time.

Understanding this trick reveals how data encoding can optimize memory in data structures.

7

Expert

Tradeoffs and Performance in Min Stack Design

🤔Before reading on: do you think the single stack encoding method is always better than two stacks? Commit to your answer.

Concept: Analyze tradeoffs between simplicity, speed, and memory in different Min Stack implementations.

Two-stack method is simple and fast but uses extra space. Single-stack encoding saves space but adds complexity and risk of bugs. Choice depends on application needs and constraints.

Result

You can choose the best Min Stack design based on your priorities.

Knowing tradeoffs helps you make informed design decisions in real-world systems.

Under the Hood

Min Stack works by storing the minimum value at each level of the stack, either alongside each element or in a separate stack. When pushing, it compares the new value with the current minimum and updates accordingly. When popping, it removes the top element and updates the minimum to the previous stored minimum. This avoids scanning the entire stack to find the minimum.

Why designed this way?

The design balances time and space efficiency. Early solutions scanned the stack for minimum, which was slow. Storing minimums at each step was introduced to achieve constant time retrieval. Using two stacks separates concerns and simplifies implementation. Single-stack encoding was later introduced to optimize space but at the cost of complexity.

Push(value):
┌───────────────┐
│ Compare value │
│ with current  │
│ minimum       │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Push value to │
│ value stack   │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Push new min  │
│ to min stack  │
└───────────────┘

Pop():
┌───────────────┐
│ Pop value from│
│ value stack   │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ If popped val │
│ equals min    │
│ pop min stack │
└───────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does the minimum value always come from the bottom of the stack? Commit to yes or no.

Common Belief: The smallest element is always at the bottom of the stack.

Reality: The minimum can be anywhere in the stack, but Min Stack tracks it at every level so it can be found instantly.

Why it matters: Assuming minimum is at bottom leads to inefficient scanning and wrong implementations.

Quick: Do you think storing only the current minimum once is enough to track minimum after pops? Commit to yes or no.

Common Belief: Storing the minimum value once is enough to know the minimum after popping elements.

Reality: You must store minimums at every push because popping can remove the current minimum, changing the minimum to a previous value.

Why it matters: Not storing minimums at every step causes incorrect minimum results after pops.

Quick: Is using a single stack with encoded values always simpler than two stacks? Commit to yes or no.

Common Belief: Single stack encoding is always simpler and better than using two stacks.

Reality: Single stack encoding saves space but is more complex and error-prone than two-stack method.

Why it matters: Choosing complex methods without need can cause bugs and maintenance issues.

Expert Zone

1

When pushing duplicate minimum values, pushing them again to the min stack ensures correct minimum tracking after pops.

2

Single stack encoding methods rely on arithmetic tricks that can overflow or cause errors if not carefully implemented.

3

In concurrent environments, Min Stack operations need synchronization to maintain correct minimum state.

When NOT to use

Min Stack is not ideal when memory is extremely limited and complexity must be minimal; in such cases, a simple stack with linear minimum search might be acceptable. For priority-based retrieval, a heap or balanced tree is better than Min Stack.

Production Patterns

Min Stack is used in real-time systems where minimum values must be accessed quickly, such as financial tickers, gaming leaderboards, or undo systems. Two-stack implementation is common for clarity, while single-stack encoding is used in embedded systems to save memory.

Connections

Heap Data Structure

Both provide quick access to minimum elements but with different performance tradeoffs.

Understanding Min Stack helps grasp how heaps maintain minimums dynamically but with different insertion and deletion costs.

Functional Programming Immutable Data

Min Stack's storing of minimum at each step resembles how immutable data structures keep snapshots of state.

Knowing Min Stack's approach clarifies how functional structures track history without mutation.

Real-time Monitoring Systems

Min Stack's constant-time minimum retrieval supports real-time data analysis and alerting.

Understanding Min Stack design aids in building efficient monitoring tools that need instant minimum or maximum values.

Common Pitfalls

#1 Not updating minimum stack when pushing new minimum values.

Wrong approach:

push(value) {
stack.push(value);
if (value < min) {
min = value;
}
// Forgot to push to min stack
}

Correct approach:

push(value) {
stack.push(value);
if (minStack.isEmpty() || value <= minStack.top()) {
minStack.push(value);
}
}

Root cause:

Misunderstanding that minimum stack must track all minimum occurrences, not just update a variable.

#2 Popping from empty stack without check causes errors.

Wrong approach:

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

Correct approach:

pop() {
if (!stack.isEmpty()) {
let val = stack.pop();
if (val === minStack.top()) {
minStack.pop();
}
}
}

Root cause:

Ignoring empty stack state leads to runtime exceptions.

#3 Assuming minimum is always at bottom and scanning stack for minimum after pop.

Wrong approach:

pop() {
stack.pop();
min = findMin(stack); // linear scan
}

Correct approach:

pop() {
let val = stack.pop();
if (val === minStack.top()) {
minStack.pop();
}
}

Root cause:

Not leveraging stored minimums causes inefficient operations.

Key Takeaways

Min Stack extends normal stack by tracking the minimum value at every step to enable instant minimum retrieval.

Storing minimums alongside values or in a separate stack avoids costly searches and keeps operations fast.

Handling edge cases like duplicates and empty stacks is crucial for correct Min Stack behavior.

Advanced implementations can optimize space but add complexity and risk, so tradeoffs must be considered.

Understanding Min Stack design helps in building efficient real-time systems and deepens knowledge of data structure optimization.

Practice

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

easy

A. To retrieve the minimum element in constant time

B. To sort elements automatically

C. To store elements in ascending order

D. To remove duplicates from the stack

Solution

1. Step 1: Understand the Min Stack functionality

   A Min Stack is designed to keep track of the minimum element efficiently while supporting normal stack operations.

2. Step 2: Identify the key feature

   The key feature is retrieving the minimum element in constant time, which normal stacks cannot do efficiently.

3. Final Answer:

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

4. Quick Check:

   Min Stack = constant time minimum retrieval [OK]

Hint: Min Stack always gives min element fast [OK]

Common Mistakes:

• Thinking it sorts elements automatically
• Confusing with normal stack behavior
• Assuming it removes duplicates

2. Which of the following is the correct TypeScript method signature to push an element x onto a Min Stack class?

easy

A. push(x: number): number

B. push(x: string): number

C. push(x: number): void

D. push(): number

Solution

1. Step 1: Understand push method requirements

   The push method should accept a number and return nothing (void) because it adds an element to the stack.

2. Step 2: Match method signature

   push(x: number): void matches: it takes a number and returns void, which is correct for push operation.

3. Final Answer:

   push(x: number): void -> Option C

4. Quick Check:

   Push method signature = push(x: number): void [OK]

Hint: Push takes number, returns void in stack [OK]

Common Mistakes:

• Using wrong parameter type like string
• Returning number instead of void
• Missing parameter in method

3. Consider the following TypeScript code for a Min Stack:

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

What will be printed?

medium

A. 2

B. 1

C. 3

D. 5

Solution

1. Step 1: Trace push and pop operations

   Push 3, 5, 2, 1 onto stack. Stack is [3,5,2,1]. Then pop removes 1. Stack is now [3,5,2].

2. Step 2: Find minimum after pop

   Minimum among [3,5,2] is 2, so getMin() returns 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Min after pop = 2 [OK]

Hint: Pop removes top; min updates accordingly [OK]

Common Mistakes:

• Forgetting pop removes last pushed element
• Assuming min stays 1 after pop
• Confusing stack order

4. The following TypeScript Min Stack implementation has a bug. What is the error?

class MinStack {
  stack: number[] = [];
  minStack: number[] = [];

  push(x: number): void {
    this.stack.push(x);
    if (this.minStack.length === 0 || x <= this.minStack[this.minStack.length - 1]) {
      this.minStack.push(x);
    }
  }

  pop(): void {
    const val = this.stack.pop();
    if (val === this.minStack[this.minStack.length - 1]) {
      this.minStack.pop();
    }
  }

  getMin(): number {
    return this.minStack[this.minStack.length - 1];
  }
}

medium

A. push() pushes to minStack even if x > current min

B. pop() does not handle empty stack case

C. getMin() returns wrong element index

D. stack array is not initialized

Solution

1. Step 1: Analyze pop() method

   pop() calls this.stack.pop() which can return undefined if stack is empty, then compares with minStack top without check.

2. Step 2: Identify missing empty check

   There is no check if stack is empty before pop, so val can be undefined causing incorrect comparison or error.

3. Final Answer:

   pop() does not handle empty stack case -> Option B

4. Quick Check:

   pop() missing empty check = bug [OK]

Hint: Always check stack empty before pop [OK]

Common Mistakes:

• Ignoring empty stack before pop
• Assuming push always pushes to minStack
• Misreading getMin index

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

hard

A. Use one stack and scan all elements to find min on getMin

B. Use a queue to store elements and find min by sorting

C. Use a linked list and traverse to find min on getMin

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

Solution

1. Step 1: Understand time complexity requirements

   All operations must be constant time, so scanning or traversing is not allowed.

2. Step 2: Identify data structure approach

   Using two stacks, one for elements and one for tracking minimums, allows constant time push, pop, and getMin.

3. Final Answer:

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

4. Quick Check:

   Two stacks = constant time min tracking [OK]

Hint: Two stacks track elements and mins fast [OK]

Common Mistakes:

• Using scanning which is not constant time
• Using queue which is not stack
• Using linked list traversal for min