Min Stack Design in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Min Stack?

A Min Stack is a special stack that supports push, pop, top operations, and can return the minimum element in constant time.

intermediate

How does a Min Stack keep track of the minimum element efficiently?

It keeps an extra stack that stores the minimum values at each level, so the current minimum is always on top of this extra stack.

beginner

What operations must a Min Stack support?

Push (add element), Pop (remove top element), Top (view top element), and GetMin (retrieve minimum element).

intermediate

Why can't we just scan the stack to find the minimum each time?

Scanning the stack each time would take linear time, making GetMin inefficient. Min Stack design keeps GetMin in constant time.

intermediate

What happens to the min stack when we pop the main stack?

We pop from the min stack only if the popped element equals the top of the min stack, to keep both stacks synchronized so the min stack always reflects the minimum of the current main stack.

What data structure is commonly used to implement a Min Stack?

A Two stacks

B Queue

C Linked list

D Hash map

A Min Stack uses two stacks: one for all elements and one for tracking minimums.

What is the time complexity to get the minimum element in a Min Stack?

A O(n)

B O(1)

C O(n log n)

D O(log n)

GetMin operation in a Min Stack is O(1) because the minimum is always on top of the min stack.

When pushing a new element, when do we push it onto the min stack?

A Only if it is smaller or equal to the current minimum

B Always

C Never

D Only if it is larger than the current minimum

We push onto the min stack only if the new element is smaller or equal to the current minimum.

What should happen to the min stack when popping the main stack?

A Never pop from min stack

B Always pop from min stack

C Pop twice from min stack

D Pop from min stack only if top elements are equal

Pop from min stack only if the popped element equals the min stack's top to keep minimum correct.

Which operation is NOT supported by a Min Stack?

A Push

B Pop

C GetMax

D GetMin

Min Stack supports GetMin but not GetMax.

Explain how a Min Stack maintains the minimum element during push and pop operations.

Think about how to keep minimum updated without scanning.

Describe the time complexity of each operation in a Min Stack and why it is efficient.

Focus on constant time operations and the role of the min stack.

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