Min Stack Design in DSA Typescript - 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.

Given the following operations, what is the output of getMin() after all operations?

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

DSA Typescript

class MinStack {
  private stack: number[] = [];
  private minStack: number[] = [];

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

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

  top(): number | undefined {
    return this.stack[this.stack.length - 1];
  }

  getMin(): number | undefined {
    return this.minStack[this.minStack.length - 1];
  }
}

const minStack = new MinStack();
minStack.push(5);
minStack.push(3);
minStack.push(7);
minStack.pop();
console.log(minStack.getMin());

A 5

B 3

C 7

D undefined

💡 Hint

Remember that getMin() returns the smallest value currently in the stack.

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

❓ Predict Output

intermediate

What is the top element after these operations on the min stack?

Using the same min stack design, what is the top element after the following operations?

push(2)
push(0)
push(3)
push(0)
pop()
getMin()
pop()
top()

DSA Typescript

class MinStack {
  private stack: number[] = [];
  private minStack: number[] = [];

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

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

  top(): number | undefined {
    return this.stack[this.stack.length - 1];
  }

  getMin(): number | undefined {
    return this.minStack[this.minStack.length - 1];
  }
}

const minStack = new MinStack();
minStack.push(2);
minStack.push(0);
minStack.push(3);
minStack.push(0);
minStack.pop();
minStack.getMin();
minStack.pop();
console.log(minStack.top());

A 0

B 2

C 3

D undefined

💡 Hint

Track the stack and min stack carefully after each operation.

After the operations, the stack is [2, 0, 3]. The top is 3, but after popping twice, the top becomes 0.

🔧 Debug

advanced

Why does this min stack implementation fail to track minimum correctly?

Look at this min stack code snippet. It does not always return the correct minimum after pop operations. Why?

class MinStack {
  private stack: number[] = [];
  private minStack: number[] = [];

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

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

  getMin(): number | undefined {
    return this.minStack[this.minStack.length - 1];
  }
}

A It does not initialize minStack before push.

B It does not pop from minStack when popping from stack.

C It uses '<' instead of '<=' in push, so equal minimums are not tracked properly.

D It uses arrays instead of linked lists, causing errors.

💡 Hint

Think about what happens when duplicate minimum values are pushed.

Using '<' instead of '<=' means equal minimum values are not pushed to minStack. When popping one minimum, the minStack loses track of the other equal minimum.

🚀 Application

advanced

How to optimize space usage in a min stack?

Which approach reduces extra space used by the min stack while still supporting getMin() in O(1) time?

A Store only the difference between current value and current minimum in the stack.

B Keep a separate stack for all elements without tracking minimum.

C Use a queue instead of a stack to track minimum.

D Store all elements twice in the stack to track minimum.

💡 Hint

Think about storing less data but still being able to find minimum quickly.

Storing differences allows reconstructing minimum without extra stack space for each element, optimizing space.

🧠 Conceptual

expert

What is the time complexity of all operations in a well-designed min stack?

For a min stack supporting push, pop, top, and getMin, what is the time complexity of each operation?

A All operations run in O(log n) time.

B Push and pop run in O(n), getMin runs in O(1).

C Top runs in O(n), others run in O(1).

D All operations run in O(1) time.

💡 Hint

Consider how the min stack tracks minimum values.

Using an auxiliary stack to track minimum allows all operations to run in constant time.

Practice

1. What is the main purpose of a Min Stack data structure?

easy

A. To retrieve the minimum element in constant time

B. To sort elements automatically

C. To store elements in ascending order

D. To remove duplicates from the stack

Solution

1. Step 1: Understand the Min Stack functionality

   A Min Stack is designed to keep track of the minimum element efficiently while supporting normal stack operations.

2. Step 2: Identify the key feature

   The key feature is retrieving the minimum element in constant time, which normal stacks cannot do efficiently.

3. Final Answer:

   To retrieve the minimum element in constant time -> Option A

4. Quick Check:

   Min Stack = constant time minimum retrieval [OK]

Hint: Min Stack always gives min element fast [OK]

Common Mistakes:

• Thinking it sorts elements automatically
• Confusing with normal stack behavior
• Assuming it removes duplicates

2. Which of the following is the correct TypeScript method signature to push an element x onto a Min Stack class?

easy

A. push(x: number): number

B. push(x: string): number

C. push(x: number): void

D. push(): number

Solution

1. Step 1: Understand push method requirements

   The push method should accept a number and return nothing (void) because it adds an element to the stack.

2. Step 2: Match method signature

   push(x: number): void matches: it takes a number and returns void, which is correct for push operation.

3. Final Answer:

   push(x: number): void -> Option C

4. Quick Check:

   Push method signature = push(x: number): void [OK]

Hint: Push takes number, returns void in stack [OK]

Common Mistakes:

• Using wrong parameter type like string
• Returning number instead of void
• Missing parameter in method

3. Consider the following TypeScript code for a Min Stack:

const minStack = new MinStack();
minStack.push(3);
minStack.push(5);
minStack.push(2);
minStack.push(1);
minStack.pop();
const min = minStack.getMin();
console.log(min);

What will be printed?

medium

A. 2

B. 1

C. 3

D. 5

Solution

1. Step 1: Trace push and pop operations

   Push 3, 5, 2, 1 onto stack. Stack is [3,5,2,1]. Then pop removes 1. Stack is now [3,5,2].

2. Step 2: Find minimum after pop

   Minimum among [3,5,2] is 2, so getMin() returns 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Min after pop = 2 [OK]

Hint: Pop removes top; min updates accordingly [OK]

Common Mistakes:

• Forgetting pop removes last pushed element
• Assuming min stays 1 after pop
• Confusing stack order

4. The following TypeScript Min Stack implementation has a bug. What is the error?

class MinStack {
  stack: number[] = [];
  minStack: number[] = [];

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

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

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

medium

A. push() pushes to minStack even if x > current min

B. pop() does not handle empty stack case

C. getMin() returns wrong element index

D. stack array is not initialized

Solution

1. Step 1: Analyze pop() method

   pop() calls this.stack.pop() which can return undefined if stack is empty, then compares with minStack top without check.

2. Step 2: Identify missing empty check

   There is no check if stack is empty before pop, so val can be undefined causing incorrect comparison or error.

3. Final Answer:

   pop() does not handle empty stack case -> Option B

4. Quick Check:

   pop() missing empty check = bug [OK]

Hint: Always check stack empty before pop [OK]

Common Mistakes:

• Ignoring empty stack before pop
• Assuming push always pushes to minStack
• Misreading getMin index

5. You want to design a Min Stack that supports push, pop, top, and getMin all in constant time. Which approach below correctly achieves this?

hard

A. Use one stack and scan all elements to find min on getMin

B. Use a queue to store elements and find min by sorting

C. Use a linked list and traverse to find min on getMin

D. Use two stacks: one for all elements, one for current mins

Solution

1. Step 1: Understand time complexity requirements

   All operations must be constant time, so scanning or traversing is not allowed.

2. Step 2: Identify data structure approach

   Using two stacks, one for elements and one for tracking minimums, allows constant time push, pop, and getMin.

3. Final Answer:

   Use two stacks: one for all elements, one for current mins -> Option D

4. Quick Check:

   Two stacks = constant time min tracking [OK]

Hint: Two stacks track elements and mins fast [OK]

Common Mistakes:

• Using scanning which is not constant time
• Using queue which is not stack
• Using linked list traversal for min