Min Stack Design in DSA Javascript - Build from Scratch

Min Stack Design

📖 Scenario: Imagine you are building a special stack for a game score tracker. This stack not only stores scores but also quickly tells you the lowest score so far. This helps players see their worst performance instantly.

🎯 Goal: You will build a MinStack class that supports these operations: push to add a score, pop to remove the last score, top to see the last score, and getMin to find the lowest score in the stack.

📋 What You'll Learn

Create a class called MinStack with a constructor

Add a method push(val) to add a value to the stack

Add a method pop() to remove the top value from the stack

Add a method top() to return the top value without removing it

Add a method getMin() to return the minimum value in the stack

Use an internal stack and a helper stack to track minimum values efficiently

💡 Why This Matters

🌍 Real World

Min stacks are useful in games, financial apps, or any system where you need to track minimum values efficiently while adding and removing data.

💼 Career

Understanding min stack design is important for coding interviews and software roles that require efficient data structure design and problem solving.

1

Create the MinStack class with constructor

Create a class called MinStack with a constructor that initializes two empty arrays: stack and minStack.

DSA Javascript

class MinStack {
  constructor() {
    // Your code here
  }
}

Hint

Use this.stack = [] and this.minStack = [] inside the constructor to create empty arrays.

2

Add the push method

Add a method called push(val) inside the MinStack class. It should add val to this.stack. Also, add val to this.minStack if minStack is empty or val is less than or equal to the last element in minStack.

DSA Javascript

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

  push(val) {
    // Your code here
  }
}

Hint

Push val to stack. For minStack, check if empty or if val is smaller or equal to current min, then push it.

3

Add the pop and top methods

Add two methods inside MinStack: pop() removes the last element from this.stack. If the popped value equals the last element in this.minStack, also remove it from minStack. Add top() that returns the last element of this.stack without removing it.

DSA Javascript

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

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

  pop() {
    // Your code here
  }

  top() {
    // Your code here
  }
}

Hint

In pop(), remove from stack and if equal to min, remove from minStack. In top(), return last element of stack.

4

Add getMin method and test output

Add a method getMin() that returns the last element of this.minStack. Then create a MinStack instance called minStack. Push -2, 0, and -3 in order. Print the result of minStack.getMin(). Then pop one element and print minStack.top() and minStack.getMin().

DSA Javascript

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

  push(val) {
    this.stack.push(val);
    if (this.minStack.length === 0 || 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();
    }
  }

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

  getMin() {
    // Your code here
  }
}

// Your code here

Hint

Return the last element of minStack in getMin(). Then test by pushing -2, 0, -3, printing min, popping, printing top and min again.

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