Min Stack Design in DSA Typescript - Execution Trace

Concept Flow - Min Stack Design

Push value

↓

Compare with current min

↓

Push value to min stack

↓

Push current min again

↓

Push value to main stack

↓

Pop value

↓

Pop from main stack and min stack

↓

Get min

↓

Return top of min stack

When pushing, compare new value with current min and push the smaller to min stack. Pop from both stacks together. Min is top of min stack.

Execution Sample

DSA Typescript

push(5)
push(3)
push(7)
pop()
getMin()

Push values 5, 3, 7; pop top; then get current minimum.

Execution Table

Step	Operation	Main Stack	Min Stack	Pointer Changes	Visual State
1	push(5)	[5]	[5]	Push 5 to main and min stacks	Main: 5 -> null, Min: 5 -> null
2	push(3)	[5, 3]	[5, 3]	3 < 5, push 3 to min stack	Main: 5 -> 3 -> null, Min: 5 -> 3 -> null
3	push(7)	[5, 3, 7]	[5, 3, 3]	7 > 3, push 3 again to min stack	Main: 5 -> 3 -> 7 -> null, Min: 5 -> 3 -> 3 -> null
4	pop()	[5, 3]	[5, 3]	Pop top from both stacks	Main: 5 -> 3 -> null, Min: 5 -> 3 -> null
5	getMin()	[5, 3]	[5, 3]	Return top of min stack: 3	Min value is 3
6	pop()	[5]	[5]	Pop top from both stacks	Main: 5 -> null, Min: 5 -> null
7	getMin()	[5]	[5]	Return top of min stack: 5	Min value is 5
8	pop()	[]	[]	Pop last element from both stacks	Both stacks empty
9	getMin()	[]	[]	Stacks empty, no min	No min value

💡 Operations stop after all pushes, pops, and getMin calls are done.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	Final
Main Stack	[]	[5]	[5,3]	[5,3,7]	[5,3]	[5,3]	[5]	[5]	[]	[]
Min Stack	[]	[5]	[5,3]	[5,3,3]	[5,3]	[5,3]	[5]	[5]	[]	[]
Current Min	null	5	3	3	3	3	5	5	null	null

Key Moments - 3 Insights

Why do we push the current min again to the min stack when the new value is greater?

Because min stack must always have the min value at the same height as main stack. See step 3 in execution_table where 7 > 3, so 3 is pushed again to keep min stack aligned.

What happens if we pop from an empty stack?

Popping from empty stacks is invalid and should be handled carefully. In execution_table step 8, after popping last element, stacks become empty, so getMin returns no min.

How does getMin return the minimum in O(1) time?

getMin returns the top of min stack instantly without traversal. See steps 5 and 7 where top of min stack is returned directly.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the top of the min stack?

A 7

B 3

C 5

D null

💡 Hint

Check the Min Stack column at step 3 in execution_table.

At which step does the main stack become empty?

A Step 8

B Step 7

C Step 5

D Step 9

💡 Hint

Look at the Main Stack column in execution_table to find when it becomes [].

If we push a value smaller than current min, what happens to min stack?

A Pop from min stack

B Push the current min again

C Push the new smaller value to min stack

D Do nothing to min stack

💡 Hint

Refer to step 2 in execution_table where 3 < 5 and 3 is pushed to min stack.

Concept Snapshot

Min Stack stores values in main stack.
Min stack stores current minimum at each push.
Push: compare new value with min stack top.
Pop: remove from both stacks.
GetMin: return top of min stack in O(1).
Keeps min tracking aligned with main stack.

Full Transcript

Min Stack uses two stacks: main stack for all values, min stack for minimums. When pushing, compare new value with current min (top of min stack). If smaller or equal, push new value to min stack; else push current min again. When popping, pop from both stacks to keep them aligned. getMin returns top of min stack instantly. This design allows retrieving minimum in constant time while supporting normal stack operations.

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