Min Stack Design in DSA Javascript - Execution Trace

Concept Flow - Min Stack Design

Push value

↓

Compare with current min

↓

Push to main stack

↓

Pop value

↓

Check if popped equals min stack top

↓

GetMin

↓

Return top of min stack

The Min Stack keeps track of the minimum value at each push by using a second stack. When pushing, it updates the min stack if needed. When popping, it also pops from the min stack if the popped value is the current minimum.

Execution Sample

DSA Javascript

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

This code pushes 5, 3, 7 onto the stack, pops the top (7), then gets the current minimum value.

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 <= current min(5), push 3 to min stack	Main: 5 -> 3 -> null; Min: 5 -> 3 -> null
3	push(7)	[5, 3, 7]	[5, 3]	7 > current min(3), min stack unchanged	Main: 5 -> 3 -> 7 -> null; Min: 5 -> 3 -> null
4	pop()	[5, 3]	[5, 3]	Pop 7 from main stack; 7 != min top(3), min stack unchanged	Main: 5 -> 3 -> null; Min: 5 -> 3 -> null
5	getMin()	[5, 3]	[5, 3]	Return top of min stack: 3	Main: 5 -> 3 -> null; Min: 5 -> 3 -> null
6	pop()	[5]	[5]	Pop 3 from main stack; 3 == min top(3), pop min stack	Main: 5 -> null; Min: 5 -> null
7	getMin()	[5]	[5]	Return top of min stack: 5	Main: 5 -> null; Min: 5 -> null
8	pop()	[]	[]	Pop 5 from main stack; 5 == min top(5), pop min stack	Main: null; Min: null
9	getMin()	[]	[]	Stack empty, no min to return	Main: null; Min: null

💡 Execution stops after all operations are performed.

Variable Tracker

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

Key Moments - 3 Insights

Why do we push the value onto the min stack only if it is smaller or equal to the current min?

Because the min stack keeps track of the minimum values at each point. If a new value is smaller or equal, it becomes the new minimum, so we push it. This is shown in steps 1 and 2 in the execution_table where min stack updates only when the pushed value is <= current min.

Why do we pop from the min stack only when the popped value equals the top of the min stack?

Because the min stack stores minimum values corresponding to the main stack. When the popped value is the current minimum, we must remove it from min stack to update the minimum. This is shown in step 6 where popping 3 also pops from min stack.

What happens if we call getMin() when the stack is empty?

There is no minimum value to return because the stack is empty. This is shown in step 9 where both stacks are empty and getMin() cannot return a value.

Visual Quiz - 3 Questions

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

A [5, 3]

B [5, 3, 7]

C [3]

D [7]

💡 Hint

Check the 'Min Stack' column at step 3 in the execution_table.

At which step does the min stack pop a value due to a pop operation on the main stack?

A Step 4

B Step 6

C Step 7

D Step 8

💡 Hint

Look for steps where 'Pointer Changes' mention popping from min stack.

If we push a value smaller than the current min, how does the min stack change?

A It stays the same

B It pops the top value

C It pushes the new smaller value on top

D It clears all values

💡 Hint

Refer to steps 1 and 2 where pushing smaller or equal values updates the min stack.

Concept Snapshot

Min Stack Design:
- Use two stacks: main stack and min stack
- Push: add to main stack; if value <= min stack top, push to min stack
- Pop: remove from main stack; if popped == min stack top, pop min stack
- getMin: return top of min stack
- Keeps track of minimum in O(1) time

Full Transcript

Min Stack Design uses two stacks to keep track of the minimum value efficiently. When pushing a value, it is added to the main stack. If this value is smaller or equal to the current minimum, it is also pushed onto the min stack. When popping, if the popped value equals the top of the min stack, it is popped from the min stack as well. The getMin operation returns the top of the min stack, which is the current minimum. This design allows retrieving the minimum value in constant time. The execution trace shows pushing values 5, 3, 7, popping 7, and getting the minimum, demonstrating how the min stack updates only when needed.

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