Min Stack Design in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of the min stack after these operations?

Consider a min stack that supports push, pop, top, and getMin operations. Starting with an empty stack, perform these operations:

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

What is the output of getMin() and top()?

DSA Javascript

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

  push(x) {
    this.stack.push(x);
    if (this.minStack.length === 0 || x <= this.minStack[this.minStack.length - 1]) {
      this.minStack.push(x);
    }
  }

  pop() {
    const val = this.stack.pop();
    if (val === this.minStack[this.minStack.length - 1]) {
      this.minStack.pop();
    }
  }

  top() {
    return this.stack[this.stack.length - 1];
  }

  getMin() {
    return this.minStack[this.minStack.length - 1];
  }
}

const minStack = new MinStack();
minStack.push(5);
minStack.push(3);
minStack.push(7);
minStack.pop();
const min = minStack.getMin();
const top = minStack.top();
console.log({min, top});

A {"min":5,"top":7}

B {"min":3,"top":3}

C {"min":3,"top":7}

D {"min":5,"top":3}

💡 Hint

Remember that pop removes the last pushed element, and getMin returns the smallest element currently in the stack.

After pushing 5, 3, and 7, the stack is [5,3,7]. Popping removes 7, so stack is [5,3]. The minimum is 3, and the top is 3.

🧠 Conceptual

intermediate

Why does Min Stack use an auxiliary stack?

In a Min Stack design, why do we use a second stack (minStack) alongside the main stack?

A To store only the maximum elements for quick max retrieval.

B To store all elements in sorted order for quick access.

C To reverse the order of elements for pop operation.

D To keep track of the minimum element at each state for O(1) getMin operation.

💡 Hint

Think about how to get the minimum element quickly without scanning the whole stack.

The auxiliary stack keeps track of the minimum element at each push, so getMin can return the current minimum in O(1) time.

🔧 Debug

advanced

What error occurs in this Min Stack implementation?

Identify the error in the following Min Stack pop method:

pop() {
const val = this.stack.pop();
if (val < this.minStack[this.minStack.length - 1]) {
this.minStack.pop();
}
}

What error or issue will this cause?

DSA Javascript

pop() {
  const val = this.stack.pop();
  if (val < this.minStack[this.minStack.length - 1]) {
    this.minStack.pop();
  }
}

A It fails to pop from minStack when val equals the current minimum, causing incorrect getMin results.

B It causes a runtime error because minStack might be empty.

C It pops from minStack too often, removing elements incorrectly.

D It causes a syntax error due to missing return statement.

💡 Hint

Check the condition that triggers popping from minStack.

The condition should check for equality (val === minStack top), not less than, to correctly update the minimum stack.

❓ Predict Output

advanced

What is the output after these Min Stack operations?

Given the following operations on an empty Min Stack:

push(2), push(2), push(1), pop(), getMin(), pop(), getMin()

What are the outputs of the two getMin() calls?

DSA Javascript

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

  push(x) {
    this.stack.push(x);
    if (this.minStack.length === 0 || x <= this.minStack[this.minStack.length - 1]) {
      this.minStack.push(x);
    }
  }

  pop() {
    const val = this.stack.pop();
    if (val === this.minStack[this.minStack.length - 1]) {
      this.minStack.pop();
    }
  }

  getMin() {
    return this.minStack[this.minStack.length - 1];
  }
}

const minStack = new MinStack();
minStack.push(2);
minStack.push(2);
minStack.push(1);
minStack.pop();
const firstMin = minStack.getMin();
minStack.pop();
const secondMin = minStack.getMin();
console.log({firstMin, secondMin});

A {"firstMin":2,"secondMin":2}

B {"firstMin":2,"secondMin":1}

C {"firstMin":1,"secondMin":2}

D {"firstMin":1,"secondMin":1}

💡 Hint

Remember minStack keeps track of minimums including duplicates.

After popping 1, min is 2. After popping one 2, min remains 2 because another 2 is still in stack.

🧠 Conceptual

expert

What is the time complexity of all Min Stack operations?

For a Min Stack implemented with two stacks (main stack and min stack), what is the time complexity of push, pop, top, and getMin operations?

A All operations run in O(n) time.

B push and pop run in O(n), top and getMin run in O(1).

C All operations run in O(1) time.

D push runs in O(1), pop runs in O(n), top and getMin run in O(1).

💡 Hint

Think about how the auxiliary stack helps avoid scanning the entire stack.

Using two stacks allows all operations to be done in constant time without scanning elements.

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