Minimum Stack (Min in O(1))

🎯

Minimum Stack (Min in O(1))

mediumSTACKAmazonGoogleFacebook

Imagine a stack of plates where you want to quickly know the smallest plate at any time without sorting or scanning all plates.

💡 This problem is about designing a stack that can return the minimum element in constant time. Beginners often struggle because a normal stack only supports push/pop/top in O(1), but finding the minimum naively requires scanning all elements, which is O(n). The challenge is to maintain minimum information efficiently.

📋

Problem Statement

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the following operations: push(x) - Push element x onto stack; pop() - Removes the element on top of the stack; top() - Get the top element; getMin() - Retrieve the minimum element in the stack.

1 ≤ number of operations ≤ 10^5-10^9 ≤ x ≤ 10^9pop, top, and getMin operations will always be called on non-empty stacks

💡

Example

Input"push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()"

Outputnull, null, null, -3, null, 0, -2

After pushing -2, 0, -3, the minimum is -3. After popping -3, top is 0 and minimum is -2.

• Only one element pushed → getMin returns that element
• All elements pushed are the same → getMin returns that element
• Strictly increasing elements pushed → getMin returns the first pushed element
• Strictly decreasing elements pushed → getMin returns the last pushed element

⚠️

Common Mistakes

Not updating min stack on push when new element equals current min

getMin returns incorrect minimum after popping duplicates

✅ Push new element onto min stack even if equal to current min

Popping min stack unconditionally on pop

Min stack and main stack get out of sync, causing wrong min

✅ Pop min stack only if popped element equals min stack top

Using min() function on stack for getMin in brute force during interviews

Code is inefficient and may time out on large inputs

✅ Explain brute force but implement optimized approach

In single stack approach, not handling negative differences correctly

Minimum value tracking breaks, causing wrong results

✅ Carefully update minVal when popping negative differences

🧠

Brute Force (Scan Entire Stack for Min)

💡 This approach exists to establish the baseline: how would you solve the problem if you had no extra data structures? It helps understand why we need optimization.

Intuition

Store elements in a normal stack. To get the minimum, scan all elements in the stack each time getMin is called.

Algorithm

1. Push elements normally onto the stack.
2. Pop elements normally from the stack.
3. For top(), return the last pushed element.
4. For getMin(), iterate through all elements in the stack to find the minimum.

💡 The difficulty is realizing that getMin is not constant time here and requires scanning all elements, which is inefficient for large inputs.

</>

Code

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

    def push(self, x: int) -> None:
        self.stack.append(x)

    def pop(self) -> None:
        self.stack.pop()

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

    def getMin(self) -> int:
        return min(self.stack)

# Driver code
if __name__ == '__main__':
    minStack = MinStack()
    minStack.push(-2)
    minStack.push(0)
    minStack.push(-3)
    print(minStack.getMin())  # Returns -3
    minStack.pop()
    print(minStack.top())     # Returns 0
    print(minStack.getMin())  # Returns -2

Line Notes

self.stack = []Initialize an empty list to simulate the stack, which will hold all elements.

self.stack.append(x)Push element x onto the stack to maintain insertion order.

self.stack.pop()Remove the top element from the stack, simulating pop operation.

return min(self.stack)Find the minimum element by scanning all elements in the stack, which is O(n).

import java.util.*;

class MinStack {
    private Stack<Integer> stack;

    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
    }

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

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

    public int getMin() {
        int min = Integer.MAX_VALUE;
        for (int val : stack) {
            if (val < min) min = val;
        }
        return min;
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin()); // -3
        minStack.pop();
        System.out.println(minStack.top());    // 0
        System.out.println(minStack.getMin()); // -2
    }
}

Line Notes

stack = new Stack<>()Initialize the stack to store elements in insertion order.

stack.push(x)Push element x onto the stack to maintain order.

stack.pop()Remove the top element from the stack.

for (int val : stack)Iterate over all elements to find the minimum, which is O(n).

#include <iostream>
#include <stack>
#include <climits>

using namespace std;

class MinStack {
    stack<int> st;
public:
    void push(int x) {
        st.push(x);
    }

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

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

    int getMin() {
        stack<int> temp = st;
        int minVal = INT_MAX;
        while (!temp.empty()) {
            minVal = min(minVal, temp.top());
            temp.pop();
        }
        return minVal;
    }
};

int main() {
    MinStack minStack;
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    cout << minStack.getMin() << endl; // -3
    minStack.pop();
    cout << minStack.top() << endl;    // 0
    cout << minStack.getMin() << endl; // -2
    return 0;
}

Line Notes

stack<int> st;Stack to hold all elements in insertion order.

st.push(x);Push element x onto the stack.

stack<int> temp = st;Copy stack to iterate without modifying original stack.

while (!temp.empty())Scan all elements to find minimum, which is O(n).

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

    push(x) {
        this.stack.push(x);
    }

    pop() {
        this.stack.pop();
    }

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

    getMin() {
        return Math.min(...this.stack);
    }
}

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

Line Notes

this.stack = []Initialize an empty array to simulate the stack.

this.stack.push(x)Push element x onto the stack.

this.stack.pop()Remove the top element from the stack.

Math.min(...this.stack)Find minimum by scanning all elements, which is O(n).

⏱

Complexity

TimeO(n) for getMin, O(1) for push/pop/top

SpaceO(n) for storing elements

Each getMin call scans all elements, so worst case O(n). Push/pop/top are O(1).

💡 For n=100000, getMin scanning all elements means 100000 operations per call, which is too slow for large inputs.

Interview Verdict: TLE for large inputs; only useful to introduce problem and motivate optimization.

This approach is too slow for interviews but helps understand why we need a better design.

🧠

Auxiliary Stack to Track Minimums

💡 This approach introduces an auxiliary stack to keep track of minimum values at each push, enabling O(1) getMin calls.

Intuition

Maintain two stacks: one for all elements, one for current minimums. When pushing, also push the new minimum onto the min stack. When popping, pop both stacks.

Algorithm

1. Initialize two stacks: main stack and min stack.
2. On push(x), push x onto main stack.
3. Push x onto min stack if min stack is empty or x <= current min.
4. On pop(), pop from main stack and if popped element equals min stack top, pop min stack too.
5. top() returns main stack top.
6. getMin() returns min stack top.

💡 The key is synchronizing the min stack with the main stack to always know the current minimum.

</>

Code

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

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self) -> None:
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()

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

    def getMin(self) -> int:
        return self.min_stack[-1]

# Driver code
if __name__ == '__main__':
    minStack = MinStack()
    minStack.push(-2)
    minStack.push(0)
    minStack.push(-3)
    print(minStack.getMin())  # -3
    minStack.pop()
    print(minStack.top())     # 0
    print(minStack.getMin())  # -2

Line Notes

self.stack = []Main stack holds all elements pushed onto the stack.

self.min_stack = []Auxiliary stack keeps track of the minimum elements at each state.

if not self.min_stack or x <= self.min_stack[-1]Push new min if stack is empty or x is smaller or equal to current min to handle duplicates.

if val == self.min_stack[-1]Pop min stack only if popped element is the current minimum to keep stacks synchronized.

import java.util.*;

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

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

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

    public void pop() {
        int val = stack.pop();
        if (val == minStack.peek()) {
            minStack.pop();
        }
    }

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

    public int getMin() {
        return minStack.peek();
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin()); // -3
        minStack.pop();
        System.out.println(minStack.top());    // 0
        System.out.println(minStack.getMin()); // -2
    }
}

Line Notes

stack = new Stack<>()Main stack stores all elements pushed.

minStack = new Stack<>()Auxiliary stack stores minimum values to enable O(1) min retrieval.

if (minStack.isEmpty() || x <= minStack.peek())Push new min if smaller or equal to current min to handle duplicates correctly.

if (val == minStack.peek())Pop min stack only if popped element equals current min to keep stacks in sync.

#include <iostream>
#include <stack>

using namespace std;

class MinStack {
    stack<int> st, minSt;
public:
    void push(int x) {
        st.push(x);
        if (minSt.empty() || x <= minSt.top()) {
            minSt.push(x);
        }
    }

    void pop() {
        if (st.top() == minSt.top()) {
            minSt.pop();
        }
        st.pop();
    }

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

    int getMin() {
        return minSt.top();
    }
};

int main() {
    MinStack minStack;
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    cout << minStack.getMin() << endl; // -3
    minStack.pop();
    cout << minStack.top() << endl;    // 0
    cout << minStack.getMin() << endl; // -2
    return 0;
}

Line Notes

stack<int> st, minSt;Two stacks: main stack for all elements, min stack for minimums.

if (minSt.empty() || x <= minSt.top())Push new min if smaller or equal to current min to handle duplicates.

if (st.top() == minSt.top())Pop min stack only if top elements match to keep stacks synchronized.

minSt.top()Current minimum element is always at the top of min stack.

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

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

    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() {
        return this.minStack[this.minStack.length - 1];
    }
}

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

Line Notes

this.stack = []Main stack stores all elements pushed.

this.minStack = []Auxiliary stack stores minimum values to enable O(1) min retrieval.

if (this.minStack.length === 0 || x <= this.minStack[this.minStack.length - 1])Push new min if smaller or equal to current min to handle duplicates.

if (val === this.minStack[this.minStack.length - 1])Pop min stack only if popped element equals current min to keep stacks synchronized.

⏱

Complexity

TimeO(1) for all operations

SpaceO(n) for two stacks storing elements

All operations are constant time because min stack tracks minimums in sync with main stack.

💡 For n=100000, all operations run efficiently in constant time, suitable for large inputs.

Interview Verdict: Accepted and optimal for interview coding.

This is the standard solution to implement and code in interviews for this problem.

🧠

Single Stack with Encoded Minimum Values

💡 This approach optimizes space by storing only one stack and encoding minimum information cleverly, avoiding a second stack.

Intuition

Store the difference between the pushed value and current minimum in the stack. Update minimum accordingly. This allows retrieving minimum in O(1) without extra stack.

Algorithm

1. Initialize an empty stack and a variable minVal.
2. On push(x), if stack empty, push 0 and set minVal = x.
3. Else push x - minVal; if x < minVal, update minVal = x.
4. On pop(), pop top; if popped value < 0, update minVal = minVal - popped value.
5. top() returns minVal if top <= 0 else minVal + top.
6. getMin() returns minVal.

💡 The trick is encoding the difference to track minimum changes without extra space.

</>

Code

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

    def push(self, x: int) -> None:
        if not self.stack:
            self.stack.append(0)
            self.minVal = x
        else:
            diff = x - self.minVal
            self.stack.append(diff)
            if diff < 0:
                self.minVal = x

    def pop(self) -> None:
        diff = self.stack.pop()
        if diff < 0:
            self.minVal = self.minVal - diff

    def top(self) -> int:
        diff = self.stack[-1]
        if diff > 0:
            return self.minVal + diff
        else:
            return self.minVal

    def getMin(self) -> int:
        return self.minVal

# Driver code
if __name__ == '__main__':
    minStack = MinStack()
    minStack.push(-2)
    minStack.push(0)
    minStack.push(-3)
    print(minStack.getMin())  # -3
    minStack.pop()
    print(minStack.top())     # 0
    print(minStack.getMin())  # -2

Line Notes

self.stack = []Stack stores differences, not actual values, to encode relative changes.

self.minVal = NoneTracks current minimum value in the stack.

diff = x - self.minValStore difference to encode new value relative to current minimum.

if diff < 0: self.minVal = xUpdate minVal if new value is smaller, reflecting new minimum.

import java.util.*;

class MinStack {
    private Stack<Long> stack;
    private long minVal;

    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push(0L);
            minVal = x;
        } else {
            long diff = (long)x - minVal;
            stack.push(diff);
            if (diff < 0) minVal = x;
        }
    }

    public void pop() {
        long diff = stack.pop();
        if (diff < 0) minVal = minVal - diff;
    }

    public int top() {
        long diff = stack.peek();
        if (diff > 0) return (int)(minVal + diff);
        else return (int)minVal;
    }

    public int getMin() {
        return (int)minVal;
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin()); // -3
        minStack.pop();
        System.out.println(minStack.top());    // 0
        System.out.println(minStack.getMin()); // -2
    }
}

Line Notes

Stack<Long> stack;Stack stores differences as long to avoid integer overflow.

minVal = x;Initialize minVal with first element pushed.

long diff = (long)x - minVal;Calculate difference to encode value relative to current min.

if (diff < 0) minVal = x;Update minVal if new value is smaller, reflecting new minimum.

#include <iostream>
#include <stack>

using namespace std;

class MinStack {
    stack<long long> st;
    long long minVal;
public:
    void push(int x) {
        if (st.empty()) {
            st.push(0);
            minVal = x;
        } else {
            long long diff = (long long)x - minVal;
            st.push(diff);
            if (diff < 0) minVal = x;
        }
    }

    void pop() {
        long long diff = st.top();
        st.pop();
        if (diff < 0) minVal = minVal - diff;
    }

    int top() {
        long long diff = st.top();
        if (diff > 0) return (int)(minVal + diff);
        else return (int)minVal;
    }

    int getMin() {
        return (int)minVal;
    }
};

int main() {
    MinStack minStack;
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    cout << minStack.getMin() << endl; // -3
    minStack.pop();
    cout << minStack.top() << endl;    // 0
    cout << minStack.getMin() << endl; // -2
    return 0;
}

Line Notes

stack<long long> st;Stack stores encoded differences as long long to prevent overflow.

st.push(0);Push zero difference for first element as baseline.

long long diff = (long long)x - minVal;Encode difference between new value and current min.

if (diff < 0) minVal = x;Update minVal if new value is smaller, reflecting new minimum.

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

    push(x) {
        if (this.stack.length === 0) {
            this.stack.push(0);
            this.minVal = x;
        } else {
            let diff = x - this.minVal;
            this.stack.push(diff);
            if (diff < 0) this.minVal = x;
        }
    }

    pop() {
        let diff = this.stack.pop();
        if (diff < 0) this.minVal = this.minVal - diff;
    }

    top() {
        let diff = this.stack[this.stack.length - 1];
        if (diff > 0) return this.minVal + diff;
        else return this.minVal;
    }

    getMin() {
        return this.minVal;
    }
}

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

Line Notes

this.stack = []Stack stores encoded differences instead of actual values.

this.minVal = nullTracks current minimum value in the stack.

let diff = x - this.minValEncode difference between new value and current minimum.

if (diff < 0) this.minVal = xUpdate minVal if new value is smaller, reflecting new minimum.

⏱

Complexity

TimeO(1) for all operations

SpaceO(n) but only one stack used

All operations are constant time and space is optimized by using one stack with encoded values.

💡 This approach saves space compared to two stacks, useful when memory is constrained.

Interview Verdict: Accepted and space optimized solution.

This is an advanced solution that impresses interviewers by optimizing space without sacrificing time.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, code the auxiliary stack approach (Approach 2) for clarity and efficiency. Approach 1 is only for explanation. Approach 3 is advanced and optional.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n) per getMin	O(n)	No	N/A	Mention only - never code
2. Auxiliary Stack	O(1) all operations	O(n) two stacks	No	N/A	Code this approach in interviews
3. Single Stack with Encoding	O(1) all operations	O(n) one stack	No	N/A	Optional advanced solution

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying requirements, then explain brute force, and progressively optimize. Practice coding and testing each approach.

How to Present

Step 1: Clarify problem constraints and operations.Step 2: Describe brute force approach and its inefficiency.Step 3: Introduce auxiliary stack approach for O(1) min retrieval.Step 4: Discuss space optimized single stack approach if time permits.Step 5: Code the chosen approach carefully and test edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of stack design, ability to optimize time and space, and coding accuracy.

Common Follow-ups

• How to handle duplicate minimum values? → Auxiliary stack stores duplicates.
• Can we optimize space further? → Use single stack with encoded differences.
• What if getMin is called on empty stack? → Clarify constraints or handle exceptions.
• How to extend for getMax in O(1)? → Use similar auxiliary stack for max.

💡 These follow-ups test your depth of understanding and ability to handle edge cases and extensions.

🔍

Pattern Recognition

When to Use

1) Need to get minimum element in a stack in O(1) time; 2) Stack supports push/pop/top; 3) Naive scanning is too slow; 4) Design data structure with auxiliary info.

Signature Phrases

retrieve minimum element in O(1)design a stack with getMinsupport push, pop, top, getMin

NOT This Pattern When

Problems that require sorting or priority queues for min/max are different patterns.

Similar Problems

Max Stack - similar auxiliary stack technique for maximumSliding Window Minimum - uses monotonic queue for minimum in windowNext Smaller Element - uses stack to find next smaller efficiently

Practice

1. Given the following code for a queue implemented with two stacks, what is the output of the last print statement?

q = MyQueue()
q.push(10)
q.push(20)
print(q.pop())
q.push(30)
print(q.peek())

easy

A. 30

B. 20

C. 10

D. Error due to empty stack

Solution

1. Step 1: Trace pop() after pushing 10 and 20

   pop_stack is empty, transfer push_stack [10,20] reversed to pop_stack [20,10], pop() returns 10.

2. Step 2: After pushing 30, peek() checks pop_stack which has [20], so peek returns 20

   After pop(), pop_stack has [20], push_stack has [30]. peek() does not transfer because pop_stack is not empty, so peek returns 20.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   pop() returns 10, peek() returns 20 [OK]

Hint: pop transfers once, peek uses existing pop_stack [OK]

Common Mistakes:

• Assuming peek returns 10 after pop
• Forgetting transfer only when pop_stack empty

2. Consider the following Python code implementing the optimized next greater element algorithm. What is the final output when calling nextGreaterElement([4,1,2], [1,3,4,2])?

easy

A. [-1, -1, 3]

B. [-1, 3, -1]

C. [3, -1, -1]

D. [3, 4, -1]

Solution

1. Step 1: Trace stack and map updates for nums2

   Process nums2: push 1, then 3 > 1 so pop 1 -> map[1]=3; push 3; 4 > 3 pop 3 -> map[3]=4; push 4; 2 < 4 push 2. Stack ends with [4,2].

2. Step 2: Assign -1 for remaining stack elements and build result

   Pop 2 -> map[2]=-1; pop 4 -> map[4]=-1. Result for nums1=[4,1,2] is [map[4], map[1], map[2]] = [-1,3,-1].

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Matches expected output from code comments and manual trace [OK]

Hint: Stack pops smaller elements when a bigger one arrives [OK]

Common Mistakes:

• Confusing order of popping leading to wrong map values
• Forgetting to assign -1 for elements with no next greater
• Mixing up indices when building the final result

3. Consider this buggy version of the decodeString function. Which line contains the subtle bug that causes incorrect decoding for inputs with multiple bracketed substrings?

medium

A. Line appending current_string to string_stack

B. Line popping count from count_stack

C. Line resetting k after '[' is missing

D. Line appending characters to current_string

Solution

1. Step 1: Identify where repeat count is reset

   After pushing k to count_stack on '[', k must be reset to 0 to avoid carryover to next substring.

2. Step 2: Locate missing reset

   The code comment indicates missing reset of k after pushing it, causing subsequent repeats to accumulate incorrectly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Resetting k prevents repeat count carryover bugs [OK]

Hint: Repeat count must reset after pushing to stack [OK]

Common Mistakes:

• Forgetting to reset repeat count after '['
• Mismanaging stack push/pop order

4. Consider this buggy implementation of the pop method in the two-stack queue. What is the bug?

def pop(self) -> int:
    while self.push_stack:
        self.pop_stack.append(self.push_stack.pop())
    return self.pop_stack.pop()

medium

A. The push_stack should be cleared after transfer to avoid duplicates.

B. The pop_stack.pop() call should be replaced with pop_stack[-1] to peek instead of pop.

C. The transfer loop should only run if pop_stack is empty, otherwise elements are transferred every pop causing inefficiency.

D. The method should check if both stacks are empty before popping to avoid runtime errors.

Solution

1. Step 1: Identify transfer condition

   The code transfers elements from push_stack to pop_stack on every pop, regardless of pop_stack state.

2. Step 2: Understand impact

   This causes O(n) time on every pop, losing amortized O(1) efficiency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Transfer only when pop_stack empty -> amortized O(1) [OK]

Hint: Transfer only if pop_stack empty to keep amortized O(1) [OK]

Common Mistakes:

• Transferring every pop causes O(n) pop time
• Not checking empty queue before pop

5. What is the time complexity of the optimal Remove K Digits algorithm using a monotonic stack on an input string of length n?

medium

A. O(n * k), because each digit can be popped up to k times

B. O(n), because each digit is pushed and popped at most once

C. O(n log n), due to sorting or priority queue operations inside the stack

D. O(n^2), because nested loops remove digits repeatedly

Solution

1. Step 1: Analyze push and pop operations

   Each digit is pushed exactly once onto the stack. Each digit can be popped at most once when a smaller digit arrives.

2. Step 2: Conclude overall complexity

   Since each digit is pushed and popped at most once, total operations are O(n), linear in input size.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Monotonic stack ensures linear time by amortized analysis [OK]

Hint: Each digit pushed/popped once -> O(n) time [OK]

Common Mistakes:

• Assuming worst case k pops per digit -> O(n*k)
• Thinking sorting or nested loops are involved