Min Stack DSA Solution - Auxiliary Stack - Study Chapter | QuizMaker

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 4: Stack & Queue

Learning Outcome

After this lesson, you should be able to design a stack that supports push, pop, top, and getMin in constant time.

Problem Statement

Design a stack that supports standard stack operations and can return the minimum element currently in the stack in O(1) time.

Brute Force Approach

Use a normal stack and scan all current values whenever getMin is called.

That makes getMin O(n), which breaks the requirement.

Optimized Approach

Store each pushed value together with the minimum value at that moment. Then the stack top always knows the current minimum.

Another valid version uses two stacks: one for values and one for minimums. The pair approach is compact and easy to dry-run.

Exact Pseudocode

stack = empty stack of (value, currentMin)
push(value):
  if stack is empty:
    currentMin = value
  else:
    currentMin = min(value, stack.top.currentMin)
  push (value, currentMin)
pop():
  pop stack
top():
  return stack.top.value
getMin():
  return stack.top.currentMin

Reference Code

class MinStack:
    def __init__(self):
        self.stack = []

    def push(self, val):
        current_min = val if not self.stack else min(val, self.stack[-1][1])
        self.stack.append((val, current_min))

    def pop(self):
        self.stack.pop()

    def top(self):
        return self.stack[-1][0]

    def getMin(self):
        return self.stack[-1][1]

class MinStack {
    stack<pair<int, int>> st;

public:
    void push(int val) {
        int currentMin = st.empty() ? val : min(val, st.top().second);
        st.push({val, currentMin});
    }

    void pop() {
        st.pop();
    }

    int top() {
        return st.top().first;
    }

    int getMin() {
        return st.top().second;
    }
};

class MinStack {
    private Deque<int[]> stack = new ArrayDeque<>();

    public void push(int val) {
        int currentMin = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
        stack.push(new int[] {val, currentMin});
    }

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

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

    public int getMin() {
        return stack.peek()[1];
    }
}

Sample Dry Run

Complexity

Edge Cases

• Duplicate minimum values.
• Negative values.
• Calling operations only when the stack is valid according to platform constraints.

Interview Checklist

• Do not scan the full stack in getMin.
• Store the minimum at each push.
• Handle duplicate minimums correctly.

FAQs

Because after a pop, the previous stack top immediately tells the previous minimum.

Yes. One stack can store values and another can store minimums. The pair approach is equivalent.

Auxiliary minimum state.

Tags

• dsa
• data structures and algorithms
• stack queue
• auxiliary stack
• medium
• interview preparation