Min Stack Design in DSA Typescript

Mental Model

A Min Stack keeps track of the smallest value at every point so you can get the minimum quickly.

Analogy: Imagine a stack of plates where each plate also has a note showing the smallest plate below it. When you add or remove plates, you update the note so you always know the smallest plate on top.

Stack top -> [value: 3, min: 1] -> [value: 1, min: 1] -> [value: 5, min: 5] -> null

Dry Run Walkthrough

Input: Push 5, Push 1, Push 3, GetMin, Pop, GetMin

Goal: Show how the stack updates and how minimum is tracked after each operation

Step 1: Push 5 onto stack

Top -> [5, min=5] -> null

Why: First element is the minimum so min is 5

Step 2: Push 1 onto stack

Top -> [1, min=1] -> [5, min=5] -> null

Why: 1 is less than previous min 5, so min updates to 1

Step 3: Push 3 onto stack

Top -> [3, min=1] -> [1, min=1] -> [5, min=5] -> null

Why: 3 is greater than current min 1, so min stays 1

Step 4: GetMin returns 1

Top -> [3, min=1] -> [1, min=1] -> [5, min=5] -> null

Why: Minimum is stored at top node, so return 1

Step 5: Pop top element (3)

Top -> [1, min=1] -> [5, min=5] -> null

Why: Remove top element, min remains 1 from next node

Step 6: GetMin returns 1

Top -> [1, min=1] -> [5, min=5] -> null

Why: Minimum is still 1 at top node

Result:

Top -> [1, min=1] -> [5, min=5] -> null
GetMin results: 1, 1

Annotated Code

DSA Typescript

class MinStack {
  private stack: {value: number; min: number}[] = [];

  push(val: number): void {
    const min = this.stack.length === 0 ? val : Math.min(val, this.getMin());
    this.stack.push({value: val, min});
  }

  pop(): void {
    if (this.stack.length > 0) {
      this.stack.pop();
    }
  }

  top(): number | null {
    if (this.stack.length === 0) return null;
    return this.stack[this.stack.length - 1].value;
  }

  getMin(): number {
    if (this.stack.length === 0) throw new Error('Stack is empty');
    return this.stack[this.stack.length - 1].min;
  }
}

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

const min = this.stack.length === 0 ? val : Math.min(val, this.getMin());

Calculate new min by comparing pushed value with current min

this.stack.push({value: val, min});

Push value and current min together to keep track

if (this.stack.length > 0) { this.stack.pop(); }

Pop top element if stack is not empty

return this.stack[this.stack.length - 1].min;

Get min from top element's stored min

Output

1

1

Complexity Analysis

Time: O(1) for push, pop, and getMin because all operations use the top element only

Space: O(n) because we store each element with its min value

vs Alternative: Compared to scanning the whole stack for min (O(n)), this design is faster by storing min at each step

Edge Cases

Empty stack getMin call

Throws error because no elements to get min from

DSA Typescript

if (this.stack.length === 0) throw new Error('Stack is empty');

Pop on empty stack

Does nothing safely without error

DSA Typescript

if (this.stack.length > 0) { this.stack.pop(); }

Push duplicate minimum values

Min remains correct because each push stores min at that point

DSA Typescript

const min = this.stack.length === 0 ? val : Math.min(val, this.getMin());

When to Use This Pattern

When you need to get the minimum value in a stack quickly at any time, use the Min Stack pattern to track minimums during push and pop.

Common Mistakes

Mistake: Only storing values without tracking minimums causes getMin to be slow or incorrect.
Fix: Store the minimum value along with each pushed element to keep track efficiently.

Summary

Keeps track of the minimum value in a stack at every push and pop.

Use when you need to retrieve the minimum element in constant time.

Store the current minimum with each element to avoid scanning the stack.

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