Min Stack Design in DSA Java - Build from Scratch

Min Stack Design

📖 Scenario: Imagine you are building a special stack for a calculator app. This stack not only stores numbers but also quickly tells you the smallest number in it at any time.

🎯 Goal: You will build a MinStack class in Java that supports push, pop, top, and getMin operations all in constant time.

📋 What You'll Learn

Create a class called MinStack with a constructor

Implement push(int val) to add a number to the stack

Implement pop() to remove the top number from the stack

Implement top() to return the top number without removing it

Implement getMin() to return the smallest number in the stack

Use only standard Java classes and no external libraries

💡 Why This Matters

🌍 Real World

Min stacks are useful in calculators, undo systems, and algorithms that need quick access to minimum values.

💼 Career

Understanding how to design efficient data structures like MinStack is important for software engineering interviews and building performant applications.

1

Create the MinStack class with two stacks

Create a public class called MinStack. Inside it, declare two private Stack<Integer> variables named stack and minStack. Initialize both stacks inside the constructor.

DSA Java

public class MinStack {
    private Stack stack;
    private Stack minStack;

    public MinStack() {
        // Your code here
    }
}

Hint

Use stack = new Stack<>(); and minStack = new Stack<>(); inside the constructor.

2

Implement the push method

Add a public method void push(int val) to the MinStack class. Inside it, push val onto stack. Then, push val onto minStack if minStack is empty or val is less than or equal to the top of minStack. Otherwise, push the current top of minStack again to keep track of the minimum.

DSA Java

import java.util.Stack;

public class MinStack {
    private Stack stack;
    private Stack minStack;

    public MinStack() {
        stack = new Stack();
        minStack = new Stack();
    }

    public void push(int val) {
        // Your code here
    }
}

Hint

Push val to stack. For minStack, push val if empty or smaller, else push the current minimum again.

3

Implement pop and top methods

Add two public methods to MinStack: void pop() which removes the top element from both stack and minStack, and int top() which returns the top element of stack without removing it.

DSA Java

import java.util.Stack;

public class MinStack {
    private Stack stack;
    private Stack minStack;

    public MinStack() {
        stack = new Stack();
        minStack = new Stack();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        } else {
            minStack.push(minStack.peek());
        }
    }

    public void pop() {
        // Your code here
    }

    public int top() {
        // Your code here
    }
}

Hint

Pop from both stacks in pop(). Return stack.peek() in top().

4

Implement getMin and print test output

Add a public method int getMin() to MinStack that returns the top element of minStack. Then, in the main method, create a MinStack object, push the numbers 5, 3, 7, and 2 in that order. Print the result of getMin(), then pop once, and print getMin() again.

DSA Java

import java.util.Stack;

public class MinStack {
    private Stack stack;
    private Stack minStack;

    public MinStack() {
        stack = new Stack();
        minStack = new Stack();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        } else {
            minStack.push(minStack.peek());
        }
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        // Your code here
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        // Your code here
    }
}

Hint

Return minStack.peek() in getMin(). In main, push 5, 3, 7, 2, print getMin(), pop once, then print getMin() again.

Practice

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

easy

A. To retrieve the minimum element in constant time along with stack operations

B. To sort elements in ascending order automatically

C. To store only the minimum elements pushed so far

D. To reverse the order of elements pushed into the stack

Solution

1. Step 1: Understand stack operations

   A stack supports push, pop, and top operations in LIFO order.

2. Step 2: Identify Min Stack feature

   Min Stack extends stack by allowing retrieval of minimum element in O(1) time.

3. Final Answer:

   To retrieve the minimum element in constant time along with stack operations -> Option A

4. Quick Check:

   Min Stack = constant time min retrieval [OK]

Hint: Min Stack always tracks minimum for O(1) min retrieval [OK]

Common Mistakes:

• Thinking Min Stack sorts elements automatically
• Assuming Min Stack stores only minimum elements
• Confusing Min Stack with reversing stack order

2. Which of the following is the correct Java method signature to push an integer val onto a Min Stack?

easy

A. public int push(int val)

B. void push(int val) public

C. public void push(int val)

D. push public void(int val)

Solution

1. Step 1: Recall Java method syntax

   Java method signature starts with access modifier, return type, method name, and parameters.

2. Step 2: Check each option

   public void push(int val) follows correct syntax: public void push(int val). Others have wrong order or return type.

3. Final Answer:

   public void push(int val) -> Option C

4. Quick Check:

   Java method syntax = public void push(int val) [OK]

Hint: Java methods start with access modifier then return type [OK]

Common Mistakes:

• Placing 'public' after method name
• Using wrong return type for void methods
• Incorrect parameter placement

3. Given the following operations on a Min Stack:

MinStack minStack = new MinStack();
minStack.push(3);
minStack.push(5);
minStack.push(2);
minStack.push(1);
minStack.pop();
int min = minStack.getMin();
System.out.println(min);

What will be printed?

medium

A. 2

B. 1

C. 3

D. 5

Solution

1. Step 1: Trace push operations and min values

   Push 3 (min=3), push 5 (min=3), push 2 (min=2), push 1 (min=1).

2. Step 2: Pop removes top (1), min updates to previous min (2), then getMin returns 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   After pop, min = 2 [OK]

Hint: Pop updates min to previous minimum [OK]

Common Mistakes:

• Assuming min stays 1 after pop
• Confusing top element with min
• Ignoring min update on pop

4. Consider this buggy Min Stack method snippet:

public void pop() {
  if(stack.isEmpty()) return;
  int top = stack.pop();
  if(top == minStack.peek()) {
    minStack.pop();
  }
}

What is the main issue here?

medium

A. It does not update minStack when pushing

B. It pops from stack twice accidentally

C. It compares top with minStack.pop() instead of peek()

D. It does not handle empty minStack before peek

Solution

1. Step 1: Analyze pop method safety

   Before calling minStack.peek(), we must ensure minStack is not empty to avoid error.

2. Step 2: Identify missing empty check on minStack

   Code checks stack but not minStack emptiness before peek, risking exception.

3. Final Answer:

   It does not handle empty minStack before peek -> Option D

4. Quick Check:

   Check minStack empty before peek [OK]

Hint: Always check stack emptiness before peek/pop [OK]

Common Mistakes:

• Ignoring minStack empty check
• Popping stack twice
• Confusing peek and pop methods

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

hard

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

B. Use two stacks: one for all values, one for current minimums

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

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

Solution

1. Step 1: Understand time complexity requirements

   All operations must be O(1), so scanning or traversing is not allowed.

2. Step 2: Evaluate approaches

   Two stacks approach keeps track of minimums efficiently in O(1) time.

3. Final Answer:

   Use two stacks: one for all values, one for current minimums -> Option B

4. Quick Check:

   Two stacks = O(1) min retrieval [OK]

Hint: Two stacks track values and minimums separately [OK]

Common Mistakes:

• Using scanning which is O(n)
• Using queue which is not stack
• Traversing linked list on getMin