Min Stack Design in DSA Javascript

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 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 keeps track of minimum values after each operation

Step 1: Push 5 onto stack; min is 5

[value: 5, min: 5] -> null

Why: First element is the minimum so far

Step 2: Push 1 onto stack; min is min(1, 5) = 1

[value: 1, min: 1] -> [value: 5, min: 5] -> null

Why: Update min to the smaller value between new and previous min

Step 3: Push 3 onto stack; min is min(3, 1) = 1

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

Why: Keep min as 1 since it is smaller than 3

Step 4: Call getMin; top min is 1

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

Why: Minimum is stored at top node for O(1) access

Step 5: Pop top element (3)

[value: 1, min: 1] -> [value: 5, min: 5] -> null

Why: Remove top and min updates to next node's min

Step 6: Call getMin; top min is 1

[value: 1, min: 1] -> [value: 5, min: 5] -> null

Why: Minimum remains 1 after pop

Result:

[value: 1, min: 1] -> [value: 5, min: 5] -> null
getMin results: 1, 1

Annotated Code

DSA Javascript

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

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

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

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

  getMin() {
    if (this.stack.length === 0) return null;
    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 with current min to keep track

this.stack.pop();

Remove top element and its min

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

Get min from top element for O(1) access

Output

1

1

Complexity Analysis

Time: O(1) for push, pop, and getMin because we store min with each element

Space: O(n) because we store min value alongside each element in the stack

vs Alternative: Naive approach scans entire stack for min on each getMin, costing O(n) time; this design keeps getMin O(1)

Edge Cases

Empty stack getMin or pop

Returns null or does nothing safely

DSA Javascript

if (this.stack.length === 0) return null;

Push duplicate minimum values

Min is correctly tracked with each duplicate

DSA Javascript

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

Pop until empty

Stack empties without error, getMin returns null

DSA Javascript

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

When to Use This Pattern

When a problem asks for retrieving the minimum element in a stack in constant time, use the Min Stack pattern to store minimums alongside values.

Common Mistakes

Mistake: Only storing values without tracking minimums causes getMin to be O(n)
Fix: Store the current minimum with each pushed element to keep getMin O(1)

Mistake: Not handling empty stack in getMin or pop leads to errors
Fix: Add checks for empty stack before accessing or popping

Summary

Keeps track of the minimum value at every stack level for quick access.

Use when you need to get the minimum element in a stack in constant time.

Store the minimum with each element so you always know the smallest value on top.

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