Min Stack Design in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the stack array in the MinStack constructor.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

A[]

B{}

Cnull

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using an object {} instead of an array.

Initializing with null or 0 which are not arrays.

The stack should be initialized as an empty array to hold the stack elements.

2fill in blank

medium

Complete the push method to add a value to the stack array.

DSA Javascript

push(val) {
  this.stack.[1](val);
}

Drag options to blanks, or click blank then click option'

Ashift

Bpop

Cpush

Dunshift

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop which removes elements.

Using shift or unshift which affect the start of the array.

The push method adds an element to the end of the array, which is how we add to the stack.

3fill in blank

hard

Fix the error in the getMin method to return the minimum value stored in the minStack array without modifying it.

DSA Javascript

getMin() {
  if (this.minStack.length === 0) return null;
  return this.minStack[this.minStack.length[1]1];
}

Drag options to blanks, or click blank then click option'

A -

B +

C *

D /

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' which accesses beyond the array.

Using other arithmetic operators like '*' or '/'.

Access the last element using `this.minStack.length - 1` to get the current minimum without popping it.

4fill in blank

hard

Fill both blanks to correctly update minStack when pushing a new value.

DSA Javascript

push(val) {
  this.stack.push(val);
  if (this.minStack.length === 0 || val [1] this.minStack[this.minStack.length - 1]) {
    this.minStack.[2](val);
  } else {
    this.minStack.push(this.minStack[this.minStack.length - 1]);
  }
}

Drag options to blanks, or click blank then click option'

A<=

Bpush

C>=

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>=' which is the wrong comparison direction.

Using 'pop' which removes instead of adding.

If the new value is less than or equal to the current min (`<=`), push it onto minStack using `push`.

5fill in blank

hard

Fill all three blanks to correctly pop from both stack and minStack.

DSA Javascript

pop() {
  if (this.stack.length === 0) return null;
  this.minStack.[1]();
  return this.stack.[2]();
}

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

Drag options to blanks, or click blank then click option'

Apop

C[]

Dshift

Attempts:

3 left

💡 Hint

Common Mistakes

Using `shift` which removes from the front.

Forgetting to initialize minStack as an empty array.

Pop from both minStack and stack using `pop()`. Initialize minStack as an empty array `[]`.

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