Why Min Stack Design in DSA Javascript?

The Big Idea

What if you could always know the smallest item in your stack instantly, no matter how big it grows?

The Scenario

Imagine you have a stack of books and you want to quickly find the smallest book without checking each one every time.

Manually, you would have to look through all the books every time you want the smallest one.

The Problem

Checking every book to find the smallest one takes a lot of time as the stack grows.

This slow process makes you wait and can cause mistakes if you lose track.

The Solution

A Min Stack keeps track of the smallest book as you add or remove books.

This way, you can always know the smallest book instantly without searching.

Before vs After

✗ Before

function getMin(stack) {
  let min = Infinity;
  for (let i = 0; i < stack.length; i++) {
    if (stack[i] < min) min = stack[i];
  }
  return min;
}

✓ After

class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = [];
  }
  push(val) {
    this.stack.push(val);
    if (!this.minStack.length || val <= this.minStack[this.minStack.length - 1]) {
      this.minStack.push(val);
    }
  }
  pop() {
    const val = this.stack.pop();
    if (val === this.minStack[this.minStack.length - 1]) {
      this.minStack.pop();
    }
    return val;
  }
  getMin() {
    return this.minStack[this.minStack.length - 1];
  }
}

What It Enables

You can instantly get the smallest value in a stack at any time, making your programs faster and smarter.

Real Life Example

In a game, quickly knowing the lowest score or smallest health value helps decide the next move without delay.

Key Takeaways

Manual search for minimum is slow and inefficient.

Min Stack keeps track of minimum values during push/pop.

Allows instant access to the smallest element anytime.

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