Implement Stack Using Queues

🎯

Implement Stack Using Queues

easySTACKAmazonBloomberg

Imagine you only have a queue data structure available, but you need to implement a stack for your application. How can you simulate the Last-In-First-Out behavior using First-In-First-Out operations?

💡 This problem is about understanding how to simulate one data structure (stack) using another (queue). Beginners often struggle because stacks and queues have opposite order behaviors, so it requires creative manipulation of queue operations to mimic stack behavior.

📋

Problem Statement

Implement a last-in-first-out (LIFO) stack using only two queues or one queue. The implemented stack should support all the functions of a normal stack: push, pop, top, and empty. Implement the MyStack class: - void push(int x) Pushes element x onto the stack. - int pop() Removes the element on top of the stack and returns it. - int top() Returns the element on the top of the stack. - boolean empty() Returns true if the stack is empty, false otherwise. Notes: - You must use only standard operations of a queue, which means only push to back, peek/pop from front, size and is empty operations are valid. - Depending on the approach, you may use one or two queues.

1 ≤ x ≤ 10^5At most 10^5 calls will be made to push, pop, top, and empty.pop and top operations will always be called on non-empty stacks.

💡

Example

Input"push(1), push(2), top(), pop(), empty()"

Output2, 2, false

After pushing 1 and 2, the top is 2. Popping removes 2. The stack is not empty after popping 2.

• pop on stack with only one element → returns that element and stack becomes empty
• top on stack with only one element → returns that element without removing it
• empty on newly created stack → returns true
• push multiple identical elements → top and pop behave correctly with duplicates

⚠️

Common Mistakes

Not swapping queues after push or pop

Subsequent operations fail because the main queue does not hold the correct elements

✅ Always swap the references of the two queues after rearrangement

Rotating the queue incorrectly in one-queue approach

Stack order is not maintained, leading to wrong pop/top results

✅ Rotate exactly len(queue) - 1 times after each push

Calling pop or top on empty stack

Runtime error or exception due to dequeuing from empty queue

✅ Check if stack is empty before pop or top, or rely on problem constraints

Using queue operations not allowed (e.g., accessing back directly)

Violates problem constraints and may not be accepted in interviews

✅ Use only standard queue operations: enqueue at back, dequeue from front, peek front

🧠

Two Queues - Push Costly

💡 This approach uses two queues and makes the push operation costly by rearranging elements to maintain stack order. It helps beginners understand how to simulate stack behavior by controlling the order of elements explicitly.

Intuition

When pushing, enqueue the new element to the empty queue, then move all elements from the other queue to this one. This way, the newest element is always at the front, simulating stack top.

Algorithm

1. Initialize two empty queues, q1 and q2.
2. To push an element x, enqueue x to q2.
3. Dequeue all elements from q1 and enqueue them to q2.
4. Swap the names of q1 and q2 so q1 always has the stack elements.
5. To pop, dequeue from q1.
6. To top, peek the front of q1.
7. To check empty, check if q1 is empty.

💡 The key is to always keep the newest element at the front of q1 by rearranging queues during push, so pop and top become simple.

</>

Code

from collections import deque

class MyStack:
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        self.q2.append(x)  # enqueue to q2
        while self.q1:
            self.q2.append(self.q1.popleft())  # move all from q1 to q2
        self.q1, self.q2 = self.q2, self.q1  # swap queues

    def pop(self) -> int:
        return self.q1.popleft()  # dequeue from q1

    def top(self) -> int:
        return self.q1[0]  # peek front of q1

    def empty(self) -> bool:
        return not self.q1

# Driver code
if __name__ == '__main__':
    stack = MyStack()
    stack.push(1)
    stack.push(2)
    print(stack.top())  # 2
    print(stack.pop())  # 2
    print(stack.empty())  # False

Line Notes

self.q2.append(x)Add new element to empty queue q2 to prepare for rearrangement

while self.q1:Move all existing elements from q1 to q2 to maintain stack order

self.q1, self.q2 = self.q2, self.q1Swap queues so q1 always holds the current stack

return self.q1.popleft()Pop the front element from q1 which is the stack top

import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    private Queue<Integer> q1;
    private Queue<Integer> q2;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        q2.offer(x); // enqueue to q2
        while (!q1.isEmpty()) {
            q2.offer(q1.poll()); // move all from q1 to q2
        }
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp; // swap queues
    }

    public int pop() {
        return q1.poll(); // dequeue from q1
    }

    public int top() {
        return q1.peek(); // peek front of q1
    }

    public boolean empty() {
        return q1.isEmpty();
    }

    // Driver
    public static void main(String[] args) {
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        System.out.println(stack.top()); // 2
        System.out.println(stack.pop()); // 2
        System.out.println(stack.empty()); // false
    }
}

Line Notes

q2.offer(x);Add new element to q2 to prepare for rearrangement

while (!q1.isEmpty())Move all elements from q1 to q2 to maintain stack order

Queue<Integer> temp = q1; q1 = q2; q2 = temp;Swap references so q1 always holds the stack

return q1.poll();Pop the front element from q1 which is the stack top

#include <iostream>
#include <queue>

using namespace std;

class MyStack {
    queue<int> q1, q2;
public:
    MyStack() {}

    void push(int x) {
        q2.push(x); // enqueue to q2
        while (!q1.empty()) {
            q2.push(q1.front());
            q1.pop(); // move all from q1 to q2
        }
        swap(q1, q2); // swap queues
    }

    int pop() {
        int val = q1.front();
        q1.pop(); // dequeue from q1
        return val;
    }

    int top() {
        return q1.front(); // peek front of q1
    }

    bool empty() {
        return q1.empty();
    }
};

// Driver
int main() {
    MyStack stack;
    stack.push(1);
    stack.push(2);
    cout << stack.top() << endl; // 2
    cout << stack.pop() << endl; // 2
    cout << (stack.empty() ? "true" : "false") << endl; // false
    return 0;
}

Line Notes

q2.push(x);Add new element to q2 to prepare for rearrangement

while (!q1.empty())Move all elements from q1 to q2 to maintain stack order

swap(q1, q2);Swap queues so q1 always holds the stack

int val = q1.front(); q1.pop();Pop the front element from q1 which is the stack top

class MyStack {
    constructor() {
        this.q1 = [];
        this.q2 = [];
    }

    push(x) {
        this.q2.push(x); // enqueue to q2
        while (this.q1.length > 0) {
            this.q2.push(this.q1.shift()); // move all from q1 to q2
        }
        [this.q1, this.q2] = [this.q2, this.q1]; // swap queues
    }

    pop() {
        return this.q1.shift(); // dequeue from q1
    }

    top() {
        return this.q1[0]; // peek front of q1
    }

    empty() {
        return this.q1.length === 0;
    }
}

// Driver
const stack = new MyStack();
stack.push(1);
stack.push(2);
console.log(stack.top()); // 2
console.log(stack.pop()); // 2
console.log(stack.empty()); // false

Line Notes

this.q2.push(x);Add new element to q2 to prepare for rearrangement

while (this.q1.length > 0)Move all elements from q1 to q2 to maintain stack order

[this.q1, this.q2] = [this.q2, this.q1];Swap queues so q1 always holds the stack

return this.q1.shift();Pop the front element from q1 which is the stack top

⏱

Complexity

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

SpaceO(n) for storing elements in queues

Each push operation moves all existing elements from q1 to q2, resulting in O(n) time per push. Pop, top, and empty are O(1) since they operate on the front of q1.

💡 For n=1000 pushes, this means up to 1,000,000 operations in worst case, which is inefficient but conceptually simple.

Interview Verdict: Accepted

This approach works correctly but is inefficient for many pushes. It is useful to understand the mechanics of simulating stack with queues.

🧠

Two Queues - Pop Costly

💡 This approach uses two queues but makes the pop operation costly by rearranging elements only when popping. It helps understand trade-offs between push and pop costs.

Intuition

Push elements normally to q1. To pop, move all elements except the last from q1 to q2, then dequeue and return the last element. Swap queues afterward.

Algorithm

1. Initialize two empty queues, q1 and q2.
2. To push, enqueue element to q1.
3. To pop, dequeue elements from q1 and enqueue to q2 until only one element remains in q1.
4. Dequeue and return the last element from q1.
5. Swap q1 and q2.
6. To top, perform similar steps as pop but re-enqueue the last element.
7. To check empty, check if q1 is empty.

💡 The key is to delay rearrangement until pop or top, keeping push simple and fast.

</>

Code

from collections import deque

class MyStack:
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        self.q1.append(x)  # enqueue to q1

    def pop(self) -> int:
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())  # move all but last to q2
        val = self.q1.popleft()  # last element is stack top
        self.q1, self.q2 = self.q2, self.q1  # swap queues
        return val

    def top(self) -> int:
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())  # move all but last to q2
        val = self.q1.popleft()  # last element is stack top
        self.q2.append(val)  # re-enqueue last element
        self.q1, self.q2 = self.q2, self.q1  # swap queues
        return val

    def empty(self) -> bool:
        return not self.q1

# Driver code
if __name__ == '__main__':
    stack = MyStack()
    stack.push(1)
    stack.push(2)
    print(stack.top())  # 2
    print(stack.pop())  # 2
    print(stack.empty())  # False

Line Notes

self.q1.append(x)Push is simple enqueue to q1

while len(self.q1) > 1:Move all but last element to q2 to isolate stack top

val = self.q1.popleft()Pop or peek the last element which is the stack top

self.q1, self.q2 = self.q2, self.q1Swap queues to prepare for next operations

import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    private Queue<Integer> q1;
    private Queue<Integer> q2;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        q1.offer(x); // enqueue to q1
    }

    public int pop() {
        while (q1.size() > 1) {
            q2.offer(q1.poll()); // move all but last to q2
        }
        int val = q1.poll(); // last element is stack top
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp; // swap queues
        return val;
    }

    public int top() {
        while (q1.size() > 1) {
            q2.offer(q1.poll()); // move all but last to q2
        }
        int val = q1.poll(); // last element is stack top
        q2.offer(val); // re-enqueue last element
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp; // swap queues
        return val;
    }

    public boolean empty() {
        return q1.isEmpty();
    }

    // Driver
    public static void main(String[] args) {
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        System.out.println(stack.top()); // 2
        System.out.println(stack.pop()); // 2
        System.out.println(stack.empty()); // false
    }
}

Line Notes

q1.offer(x);Push is simple enqueue to q1

while (q1.size() > 1)Move all but last element to q2 to isolate stack top

int val = q1.poll();Pop or peek the last element which is the stack top

Queue<Integer> temp = q1; q1 = q2; q2 = temp;Swap queues to prepare for next operations

#include <iostream>
#include <queue>

using namespace std;

class MyStack {
    queue<int> q1, q2;
public:
    MyStack() {}

    void push(int x) {
        q1.push(x); // enqueue to q1
    }

    int pop() {
        while (q1.size() > 1) {
            q2.push(q1.front());
            q1.pop(); // move all but last to q2
        }
        int val = q1.front();
        q1.pop(); // last element is stack top
        swap(q1, q2); // swap queues
        return val;
    }

    int top() {
        while (q1.size() > 1) {
            q2.push(q1.front());
            q1.pop(); // move all but last to q2
        }
        int val = q1.front();
        q1.pop();
        q2.push(val); // re-enqueue last element
        swap(q1, q2); // swap queues
        return val;
    }

    bool empty() {
        return q1.empty();
    }
};

// Driver
int main() {
    MyStack stack;
    stack.push(1);
    stack.push(2);
    cout << stack.top() << endl; // 2
    cout << stack.pop() << endl; // 2
    cout << (stack.empty() ? "true" : "false") << endl; // false
    return 0;
}

Line Notes

q1.push(x);Push is simple enqueue to q1

while (q1.size() > 1)Move all but last element to q2 to isolate stack top

int val = q1.front(); q1.pop();Pop or peek the last element which is the stack top

swap(q1, q2);Swap queues to prepare for next operations

class MyStack {
    constructor() {
        this.q1 = [];
        this.q2 = [];
    }

    push(x) {
        this.q1.push(x); // enqueue to q1
    }

    pop() {
        while (this.q1.length > 1) {
            this.q2.push(this.q1.shift()); // move all but last to q2
        }
        const val = this.q1.shift(); // last element is stack top
        [this.q1, this.q2] = [this.q2, this.q1]; // swap queues
        return val;
    }

    top() {
        while (this.q1.length > 1) {
            this.q2.push(this.q1.shift()); // move all but last to q2
        }
        const val = this.q1.shift();
        this.q2.push(val); // re-enqueue last element
        [this.q1, this.q2] = [this.q2, this.q1]; // swap queues
        return val;
    }

    empty() {
        return this.q1.length === 0;
    }
}

// Driver
const stack = new MyStack();
stack.push(1);
stack.push(2);
console.log(stack.top()); // 2
console.log(stack.pop()); // 2
console.log(stack.empty()); // false

Line Notes

this.q1.push(x);Push is simple enqueue to q1

while (this.q1.length > 1)Move all but last element to q2 to isolate stack top

const val = this.q1.shift();Pop or peek the last element which is the stack top

[this.q1, this.q2] = [this.q2, this.q1];Swap queues to prepare for next operations

⏱

Complexity

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

SpaceO(n) for storing elements in queues

Push is O(1) as it just enqueues. Pop and top require moving n-1 elements between queues, so O(n) time.

💡 For n=1000 pops, this means up to 1,000,000 operations in worst case, which is inefficient but push is fast.

Interview Verdict: Accepted

This approach balances costs differently than approach 1, useful to understand trade-offs in design.

🧠

One Queue - Push Costly (Rotate Queue)

💡 This approach uses a single queue and makes push costly by rotating the queue to keep the newest element at the front. It is the most optimal and elegant solution for this problem.

Intuition

After pushing an element, rotate the queue by dequeuing and enqueuing all previous elements behind the new element, so the new element is always at the front.

Algorithm

1. Initialize an empty queue q.
2. To push x, enqueue x to q.
3. Rotate the queue by dequeuing and enqueuing all elements except the newly added one.
4. To pop, dequeue from q.
5. To top, peek the front of q.
6. To check empty, check if q is empty.

💡 The rotation after push ensures the newest element is always at the front, so pop and top are O(1).

</>

Code

from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)  # enqueue
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())  # rotate queue

    def pop(self) -> int:
        return self.q.popleft()  # dequeue front

    def top(self) -> int:
        return self.q[0]  # peek front

    def empty(self) -> bool:
        return not self.q

# Driver code
if __name__ == '__main__':
    stack = MyStack()
    stack.push(1)
    stack.push(2)
    print(stack.top())  # 2
    print(stack.pop())  # 2
    print(stack.empty())  # False

Line Notes

self.q.append(x)Add new element to the queue

for _ in range(len(self.q) - 1)Rotate queue to move new element to front

self.q.append(self.q.popleft())Dequeue front and enqueue at back to rotate

return self.q.popleft()Pop the front element which is the stack top

import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    private Queue<Integer> q;

    public MyStack() {
        q = new LinkedList<>();
    }

    public void push(int x) {
        q.offer(x); // enqueue
        int size = q.size();
        for (int i = 0; i < size - 1; i++) {
            q.offer(q.poll()); // rotate queue
        }
    }

    public int pop() {
        return q.poll(); // dequeue front
    }

    public int top() {
        return q.peek(); // peek front
    }

    public boolean empty() {
        return q.isEmpty();
    }

    // Driver
    public static void main(String[] args) {
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        System.out.println(stack.top()); // 2
        System.out.println(stack.pop()); // 2
        System.out.println(stack.empty()); // false
    }
}

Line Notes

q.offer(x);Add new element to the queue

for (int i = 0; i < size - 1; i++)Rotate queue to move new element to front

q.offer(q.poll());Dequeue front and enqueue at back to rotate

return q.poll();Pop the front element which is the stack top

#include <iostream>
#include <queue>

using namespace std;

class MyStack {
    queue<int> q;
public:
    MyStack() {}

    void push(int x) {
        q.push(x); // enqueue
        int size = q.size();
        for (int i = 0; i < size - 1; i++) {
            q.push(q.front());
            q.pop(); // rotate queue
        }
    }

    int pop() {
        int val = q.front();
        q.pop(); // dequeue front
        return val;
    }

    int top() {
        return q.front(); // peek front
    }

    bool empty() {
        return q.empty();
    }
};

// Driver
int main() {
    MyStack stack;
    stack.push(1);
    stack.push(2);
    cout << stack.top() << endl; // 2
    cout << stack.pop() << endl; // 2
    cout << (stack.empty() ? "true" : "false") << endl; // false
    return 0;
}

Line Notes

q.push(x);Add new element to the queue

for (int i = 0; i < size - 1; i++)Rotate queue to move new element to front

q.push(q.front()); q.pop();Dequeue front and enqueue at back to rotate

int val = q.front(); q.pop();Pop the front element which is the stack top

class MyStack {
    constructor() {
        this.q = [];
    }

    push(x) {
        this.q.push(x); // enqueue
        let size = this.q.length;
        for (let i = 0; i < size - 1; i++) {
            this.q.push(this.q.shift()); // rotate queue
        }
    }

    pop() {
        return this.q.shift(); // dequeue front
    }

    top() {
        return this.q[0]; // peek front
    }

    empty() {
        return this.q.length === 0;
    }
}

// Driver
const stack = new MyStack();
stack.push(1);
stack.push(2);
console.log(stack.top()); // 2
console.log(stack.pop()); // 2
console.log(stack.empty()); // false

Line Notes

this.q.push(x);Add new element to the queue

for (let i = 0; i < size - 1; i++)Rotate queue to move new element to front

this.q.push(this.q.shift());Dequeue front and enqueue at back to rotate

return this.q.shift();Pop the front element which is the stack top

⏱

Complexity

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

SpaceO(n) for storing elements in queue

Push rotates the queue by moving n-1 elements, so O(n) time. Pop and top are O(1) since they operate on the front.

💡 For n=1000 pushes, this means up to 1,000,000 operations, but pop/top are very fast.

Interview Verdict: Accepted

This is the most optimal and elegant approach, recommended for interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 The one-queue rotation approach is recommended for interviews due to its elegance and efficiency. The two-queue approaches are useful for understanding but less optimal.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Two Queues - Push Costly	Push: O(n), Pop/Top: O(1)	O(n)	No	N/A	Mention only - good for conceptual understanding
2. Two Queues - Pop Costly	Push: O(1), Pop/Top: O(n)	O(n)	No	N/A	Mention only - shows trade-offs
3. One Queue - Push Costly (Rotate)	Push: O(n), Pop/Top: O(1)	O(n)	No	N/A	Code this approach in 95% of interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying requirements, then explain the brute force approach, and progressively optimize. Practice coding and testing all edge cases.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach using two queues with costly push.Step 3: Discuss the alternative with costly pop and trade-offs.Step 4: Present the optimal one-queue rotation approach.Step 5: Code the chosen approach and test with examples and edge cases.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your understanding of queue and stack operations, your ability to simulate one data structure with another, and your skill in optimizing time and space complexity.

Common Follow-ups

• Can you implement the stack using only one queue? → Use rotation technique.
• What is the time complexity trade-off between push and pop in your approaches? → Explain push costly vs pop costly.
• How would you implement a queue using stacks? → Reverse the roles and use two stacks.
• Can you optimize space usage? → Use one queue instead of two.

💡 These follow-ups test your flexibility in design and understanding of data structure dualities.

🔍

Pattern Recognition

When to Use

1) Asked to implement stack using queues; 2) Only queue operations allowed; 3) Need to simulate LIFO with FIFO; 4) Design problem involving data structure simulation.

Signature Phrases

Implement stack using queuesUse only queue operationsSimulate LIFO with FIFO

NOT This Pattern When

Problems that ask for direct stack or queue implementation without simulation or design constraints.

Similar Problems

Implement Queue using Stacks - inverse problem of simulating queue with stacksMin Stack - stack design with additional constraintsMax Stack - similar design problem with max retrieval

Practice

1. You are given a list of asteroids represented by integers where the absolute value represents size and the sign represents direction (positive moving right, negative moving left). When two asteroids moving in opposite directions collide, the smaller one explodes. Which algorithmic approach guarantees an optimal solution to determine the state of asteroids after all collisions?

easy

A. Sorting asteroids by size and simulating collisions from largest to smallest

B. Greedy approach that removes pairs of colliding asteroids in a single pass without revisiting previous elements

C. Dynamic programming that stores subproblems of asteroid states to avoid recomputation

D. Stack simulation that processes asteroids sequentially, resolving collisions by comparing the current asteroid with the top of the stack

Solution

1. Step 1: Understand the collision condition

   Collisions only happen when a right-moving asteroid (positive) meets a left-moving asteroid (negative) coming after it.

2. Step 2: Recognize stack simulation suitability

   A stack naturally models the sequence of asteroids and allows checking the last asteroid's direction and size to resolve collisions efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Stack approach handles direction and size checks correctly [OK]

Hint: Stack simulates collisions by tracking last asteroid [OK]

Common Mistakes:

• Assuming greedy single pass without stack handles all cases
• Using DP unnecessarily
• Sorting breaks order-dependent collisions

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. You are given a numeric string num and an integer k. The task is to remove exactly k digits from num to produce the smallest possible number. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Greedy algorithm using a monotonic increasing stack to remove digits that are greater than the next digit

B. Dynamic Programming that tries all subsequences of length n-k and picks the smallest lexicographically

C. Simple greedy approach removing the largest digits from left to right without considering order

D. Brute force generating all combinations of digits to remove and selecting the minimal result

Solution

1. Step 1: Understand the problem constraints

   The problem requires removing digits to minimize the resulting number, which suggests a greedy approach that considers digit order.

2. Step 2: Identify the optimal approach

   Using a monotonic increasing stack allows removing digits that are larger than the next digit, ensuring the smallest possible number in O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack approach is known optimal for this problem [OK]

Hint: Monotonic stack greedily removes bigger digits before smaller ones [OK]

Common Mistakes:

• Assuming simple greedy removing largest digits left to right is optimal
• Thinking DP is needed for minimal number subsequence

4. What is the time complexity of the optimal monotonic stack algorithm for detecting the 132 pattern in an array of length n?

medium

A. O(n) because each element is pushed and popped at most once

B. O(n^2) due to nested loops inside the stack operations

C. O(n log n) due to sorting implicit in stack operations

D. O(n^3) because of triple nested conditions

Solution

1. Step 1: Identify operations per element

   Each element is pushed onto the stack once and popped at most once, so total stack operations are O(n).

2. Step 2: Confirm no nested loops

   The algorithm iterates once over the array, with inner while loop popping elements but total pops across all iterations sum to n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time confirmed by amortized stack operations [OK]

Hint: Stack push/pop amortized to O(n) total [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Thinking stack operations imply sorting
• Confusing with brute force complexity

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