Implement Queue Using Stacks

🎯

Implement Queue Using Stacks

easySTACKAmazonBloombergGoogle

Imagine you have two stacks of plates and want to simulate a queue behavior - first in, first out - using only these stacks.

💡 This problem teaches how to simulate one data structure (queue) using another (stack). Beginners often struggle because stacks are LIFO and queues are FIFO, so the challenge is to reverse the order using stack operations.

📋

Problem Statement

Implement a queue using two stacks. The queue should support the following operations: push(x) to add element x to the back of the queue, pop() to remove the element from the front of the queue, peek() to get the front element, and empty() to check if the queue is empty.

1 ≤ number of operations ≤ 10^5All operations are valid (e.g., pop or peek will not be called on an empty queue).

💡

Example

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

Output1, 1, false

After pushing 1 and 2, peek returns 1 (front). Pop removes 1. empty returns false because 2 is still in queue.

• pop on queue with one element → queue becomes empty
• peek on queue with one element → returns that element
• empty on newly created queue → returns true
• push multiple elements then pop all → queue empties correctly

⚠️

Common Mistakes

Transferring elements on every pop instead of only when pop stack is empty

Causes O(n) time for every pop, losing amortized efficiency

✅ Transfer elements only if pop stack is empty

Not handling empty queue before pop or peek

Runtime error or exception when popping from empty stack

✅ Check if both stacks are empty before pop/peek and handle accordingly

Using one stack with recursion but forgetting to restore stack after pop

Stack loses elements, queue order breaks

✅ Push back all popped elements after recursive pop call

Confusing push and pop stacks roles

Queue order is reversed incorrectly, wrong outputs

✅ Keep push stack for incoming elements, pop stack for outgoing elements

🧠

Brute Force (Using One Stack and Recursion for Pop)

💡 This approach shows the naive way to simulate queue behavior using a single stack and recursion to reverse order during pop. It is inefficient but helps understand the problem's core challenge.

Intuition

Use one stack to store elements. To pop the front element, recursively pop all elements until the bottom is reached, then rebuild the stack.

Algorithm

1. Push elements onto the stack normally.
2. To pop, recursively pop elements until the bottom is reached.
3. Return the bottom element as the popped value.
4. Push back all other elements to restore stack order.

💡 The recursion hides the complexity of reversing the stack order, but it is costly and not practical for large inputs.

</>

Code

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

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

    def pop(self) -> int:
        if len(self.stack) == 1:
            return self.stack.pop()
        x = self.stack.pop()
        res = self.pop()
        self.stack.append(x)
        return res

    def peek(self) -> int:
        res = self.pop()
        self.stack.append(res)
        return res

    def empty(self) -> bool:
        return len(self.stack) == 0

# Driver code
if __name__ == '__main__':
    q = MyQueue()
    q.push(1)
    q.push(2)
    print(q.peek())  # Output: 1
    print(q.pop())   # Output: 1
    print(q.empty()) # Output: False

Line Notes

self.stack = []Initialize the stack to hold queue elements

self.stack.append(x)Restore popped elements after bottom is removed

if len(self.stack) == 1:Base case: bottom element reached for pop operation

x = self.stack.pop()Pop top element to reach bottom recursively

res = self.pop()Peek uses pop to get front element without removing permanently

return len(self.stack) == 0Empty checks if stack has no elements

import java.util.Stack;

class MyQueue {
    private Stack<Integer> stack;

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

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

    public int pop() {
        if (stack.size() == 1) {
            return stack.pop();
        }
        int x = stack.pop();
        int res = pop();
        stack.push(x);
        return res;
    }

    public int peek() {
        int res = pop();
        stack.push(res);
        return res;
    }

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

    public static void main(String[] args) {
        MyQueue q = new MyQueue();
        q.push(1);
        q.push(2);
        System.out.println(q.peek());  // 1
        System.out.println(q.pop());   // 1
        System.out.println(q.empty()); // false
    }
}

Line Notes

stack = new Stack<>()Initialize stack to hold elements

stack.push(x)Restore popped elements after bottom is removed

if (stack.size() == 1)Base case: bottom element reached for pop operation

int x = stack.pop()Pop top element to reach bottom recursively

int res = pop()Peek uses pop to get front element without removing permanently

return stack.isEmpty()Check if stack is empty

#include <iostream>
#include <stack>
using namespace std;

class MyQueue {
    stack<int> st;
public:
    MyQueue() {}

    void push(int x) {
        st.push(x);
    }

    int pop() {
        if (st.size() == 1) {
            int val = st.top();
            st.pop();
            return val;
        }
        int x = st.top();
        st.pop();
        int res = pop();
        st.push(x);
        return res;
    }

    int peek() {
        int res = pop();
        st.push(res);
        return res;
    }

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

int main() {
    MyQueue q;
    q.push(1);
    q.push(2);
    cout << q.peek() << endl;  // 1
    cout << q.pop() << endl;   // 1
    cout << (q.empty() ? "true" : "false") << endl; // false
    return 0;
}

Line Notes

stack<int> st;Stack to hold queue elements

st.push(x);Restore popped elements after bottom is removed

if (st.size() == 1)Base case: bottom element reached for pop operation

int x = st.top();Pop top element to reach bottom recursively

int res = pop();Peek uses pop to get front element without removing permanently

return st.empty();Check if stack is empty

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

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

    pop() {
        if (this.stack.length === 1) {
            return this.stack.pop();
        }
        let x = this.stack.pop();
        let res = this.pop();
        this.stack.push(x);
        return res;
    }

    peek() {
        let res = this.pop();
        this.stack.push(res);
        return res;
    }

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

// Driver code
const q = new MyQueue();
q.push(1);
q.push(2);
console.log(q.peek());  // 1
console.log(q.pop());   // 1
console.log(q.empty()); // false

Line Notes

this.stack = []Initialize stack to hold elements

this.stack.push(x)Restore popped elements after bottom is removed

if (this.stack.length === 1)Base case: bottom element reached for pop operation

let x = this.stack.pop()Pop top element to reach bottom recursively

let res = this.pop()Peek uses pop to get front element without removing permanently

return this.stack.length === 0Check if stack is empty

⏱

Complexity

TimeO(n) per pop/peek in worst case due to recursion

SpaceO(n) for stack and recursion call stack

Each pop or peek may recursively pop all elements to reach the bottom, causing O(n) time per operation.

💡 For n=20, popping one element may require up to 20 recursive calls, which is inefficient.

Interview Verdict: Accepted but inefficient; not suitable for large inputs

This approach works but is too slow for large inputs; it helps understand the problem but is not practical.

🧠

Two Stacks with Push Costly (Transfer on Push)

💡 This approach uses two stacks to maintain queue order by transferring elements on every push, ensuring pop and peek are O(1). It is easier to understand but less efficient overall.

Intuition

Keep one stack for queue front and one for queue back. On push, move all elements to the back stack, push new element, then move all back to front stack.

Algorithm

1. On push, move all elements from front stack to back stack.
2. Push new element onto back stack.
3. Move all elements back to front stack.
4. Pop and peek operate directly on front stack.

💡 This approach reverses the stack twice on every push to maintain queue order, making push O(n) but pop/peek O(1).

</>

Code

class MyQueue:
    def __init__(self):
        self.front = []
        self.back = []

    def push(self, x: int) -> None:
        while self.front:
            self.back.append(self.front.pop())
        self.back.append(x)
        while self.back:
            self.front.append(self.back.pop())

    def pop(self) -> int:
        return self.front.pop()

    def peek(self) -> int:
        return self.front[-1]

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

# Driver code
if __name__ == '__main__':
    q = MyQueue()
    q.push(1)
    q.push(2)
    print(q.peek())  # 1
    print(q.pop())   # 1
    print(q.empty()) # False

Line Notes

self.front = []Stack to hold queue front elements for pop and peek

self.back = []Temporary stack for transferring elements during push

while self.front:Move all elements to back stack to reverse order before push

self.back.append(x)Push new element onto back stack

while self.back:Move elements back to front stack to restore queue order

return self.front.pop()Pop front element from front stack efficiently

return self.front[-1]Peek front element from front stack efficiently

return not self.frontCheck if front stack is empty to determine if queue is empty

import java.util.Stack;

class MyQueue {
    private Stack<Integer> front;
    private Stack<Integer> back;

    public MyQueue() {
        front = new Stack<>();
        back = new Stack<>();
    }

    public void push(int x) {
        while (!front.isEmpty()) {
            back.push(front.pop());
        }
        back.push(x);
        while (!back.isEmpty()) {
            front.push(back.pop());
        }
    }

    public int pop() {
        return front.pop();
    }

    public int peek() {
        return front.peek();
    }

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

    public static void main(String[] args) {
        MyQueue q = new MyQueue();
        q.push(1);
        q.push(2);
        System.out.println(q.peek());  // 1
        System.out.println(q.pop());   // 1
        System.out.println(q.empty()); // false
    }
}

Line Notes

front = new Stack<>()Stack to hold queue front elements for pop and peek

back = new Stack<>()Temporary stack for transferring elements during push

while (!front.isEmpty())Move all elements to back stack to reverse order before push

back.push(x)Push new element onto back stack

while (!back.isEmpty())Move elements back to front stack to restore queue order

return front.pop()Pop front element from front stack efficiently

return front.peek()Peek front element from front stack efficiently

return front.isEmpty()Check if front stack is empty to determine if queue is empty

#include <iostream>
#include <stack>
using namespace std;

class MyQueue {
    stack<int> front, back;
public:
    MyQueue() {}

    void push(int x) {
        while (!front.empty()) {
            back.push(front.top());
            front.pop();
        }
        back.push(x);
        while (!back.empty()) {
            front.push(back.top());
            back.pop();
        }
    }

    int pop() {
        int val = front.top();
        front.pop();
        return val;
    }

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

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

int main() {
    MyQueue q;
    q.push(1);
    q.push(2);
    cout << q.peek() << endl;  // 1
    cout << q.pop() << endl;   // 1
    cout << (q.empty() ? "true" : "false") << endl; // false
    return 0;
}

Line Notes

stack<int> front, back;Two stacks for queue front and temporary back during push

while (!front.empty())Move all elements to back stack to reverse order before push

back.push(x);Push new element onto back stack

while (!back.empty())Move elements back to front stack to restore queue order

int val = front.top();Pop front element from front stack efficiently

return front.top();Peek front element from front stack efficiently

return front.empty();Check if front stack is empty to determine if queue is empty

class MyQueue {
    constructor() {
        this.front = [];
        this.back = [];
    }

    push(x) {
        while (this.front.length > 0) {
            this.back.push(this.front.pop());
        }
        this.back.push(x);
        while (this.back.length > 0) {
            this.front.push(this.back.pop());
        }
    }

    pop() {
        return this.front.pop();
    }

    peek() {
        return this.front[this.front.length - 1];
    }

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

// Driver code
const q = new MyQueue();
q.push(1);
q.push(2);
console.log(q.peek());  // 1
console.log(q.pop());   // 1
console.log(q.empty()); // false

Line Notes

this.front = []Stack to hold queue front elements for pop and peek

this.back = []Temporary stack for transferring elements during push

while (this.front.length > 0)Move all elements to back stack to reverse order before push

this.back.push(x)Push new element onto back stack

while (this.back.length > 0)Move elements back to front stack to restore queue order

return this.front.pop()Pop front element from front stack efficiently

return this.front[this.front.length - 1]Peek front element from front stack efficiently

return this.front.length === 0Check if front stack is empty to determine if queue is empty

⏱

Complexity

TimeO(n) per push, O(1) per pop/peek

SpaceO(n) for two stacks

Push requires moving all elements twice, so O(n). Pop and peek are O(1) since front stack is ready.

💡 For n=20 pushes, each push may move 20 elements twice, totaling 800 operations; pop is fast.

Interview Verdict: Accepted but push is costly; better than brute force for pop/peek

This approach improves pop/peek but push is expensive, so not optimal for many pushes.

🧠

Two Stacks with Pop Costly (Amortized O(1)) - Optimal

💡 This is the standard optimal approach using two stacks: one for push, one for pop. Elements are transferred only when needed, achieving amortized O(1) per operation.

Intuition

Use one stack to push new elements. For pop or peek, if pop stack is empty, transfer all elements from push stack to pop stack to reverse order, then pop/peek from pop stack.

Algorithm

1. Push elements onto the push stack.
2. For pop or peek, if pop stack is empty, transfer all elements from push stack to pop stack.
3. Pop or peek from pop stack.
4. Empty checks if both stacks are empty.

💡 This lazy transfer ensures each element moves at most twice, making operations efficient overall.

</>

Code

class MyQueue:
    def __init__(self):
        self.push_stack = []
        self.pop_stack = []

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

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

    def peek(self) -> int:
        if not self.pop_stack:
            while self.push_stack:
                self.pop_stack.append(self.push_stack.pop())
        return self.pop_stack[-1]

    def empty(self) -> bool:
        return not self.push_stack and not self.pop_stack

# Driver code
if __name__ == '__main__':
    q = MyQueue()
    q.push(1)
    q.push(2)
    print(q.peek())  # 1
    print(q.pop())   # 1
    print(q.empty()) # False

Line Notes

self.push_stack = []Stack to hold pushed elements before transfer

self.pop_stack = []Stack to hold elements for popping in queue order

self.push_stack.append(x)Push new element onto push stack efficiently

if not self.pop_stack:Transfer elements only if pop stack is empty to maintain order

while self.push_stack:Move all elements from push to pop stack to reverse order

return self.pop_stack.pop()Pop front element from pop stack efficiently

return self.pop_stack[-1]Peek front element from pop stack efficiently

return not self.push_stack and not self.pop_stackQueue empty if both stacks are empty

import java.util.Stack;

class MyQueue {
    private Stack<Integer> pushStack;
    private Stack<Integer> popStack;

    public MyQueue() {
        pushStack = new Stack<>();
        popStack = new Stack<>();
    }

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

    public int pop() {
        if (popStack.isEmpty()) {
            while (!pushStack.isEmpty()) {
                popStack.push(pushStack.pop());
            }
        }
        return popStack.pop();
    }

    public int peek() {
        if (popStack.isEmpty()) {
            while (!pushStack.isEmpty()) {
                popStack.push(pushStack.pop());
            }
        }
        return popStack.peek();
    }

    public boolean empty() {
        return pushStack.isEmpty() && popStack.isEmpty();
    }

    public static void main(String[] args) {
        MyQueue q = new MyQueue();
        q.push(1);
        q.push(2);
        System.out.println(q.peek());  // 1
        System.out.println(q.pop());   // 1
        System.out.println(q.empty()); // false
    }
}

Line Notes

pushStack = new Stack<>()Stack to hold pushed elements before transfer

popStack = new Stack<>()Stack to hold elements for popping in queue order

pushStack.push(x)Push new element onto push stack efficiently

if (popStack.isEmpty())Transfer elements only if pop stack is empty to maintain order

while (!pushStack.isEmpty())Move all elements from push to pop stack to reverse order

return popStack.pop()Pop front element from pop stack efficiently

return popStack.peek()Peek front element from pop stack efficiently

return pushStack.isEmpty() && popStack.isEmpty()Queue empty if both stacks are empty

#include <iostream>
#include <stack>
using namespace std;

class MyQueue {
    stack<int> pushStack, popStack;
public:
    MyQueue() {}

    void push(int x) {
        pushStack.push(x);
    }

    int pop() {
        if (popStack.empty()) {
            while (!pushStack.empty()) {
                popStack.push(pushStack.top());
                pushStack.pop();
            }
        }
        int val = popStack.top();
        popStack.pop();
        return val;
    }

    int peek() {
        if (popStack.empty()) {
            while (!pushStack.empty()) {
                popStack.push(pushStack.top());
                pushStack.pop();
            }
        }
        return popStack.top();
    }

    bool empty() {
        return pushStack.empty() && popStack.empty();
    }
};

int main() {
    MyQueue q;
    q.push(1);
    q.push(2);
    cout << q.peek() << endl;  // 1
    cout << q.pop() << endl;   // 1
    cout << (q.empty() ? "true" : "false") << endl; // false
    return 0;
}

Line Notes

stack<int> pushStack, popStack;Two stacks for push and pop operations

pushStack.push(x);Push new element onto push stack efficiently

if (popStack.empty())Transfer elements only if pop stack is empty to maintain order

while (!pushStack.empty())Move all elements from push to pop stack to reverse order

int val = popStack.top();Pop front element from pop stack efficiently

return popStack.top();Peek front element from pop stack efficiently

return pushStack.empty() && popStack.empty();Queue empty if both stacks are empty

class MyQueue {
    constructor() {
        this.pushStack = [];
        this.popStack = [];
    }

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

    pop() {
        if (this.popStack.length === 0) {
            while (this.pushStack.length > 0) {
                this.popStack.push(this.pushStack.pop());
            }
        }
        return this.popStack.pop();
    }

    peek() {
        if (this.popStack.length === 0) {
            while (this.pushStack.length > 0) {
                this.popStack.push(this.pushStack.pop());
            }
        }
        return this.popStack[this.popStack.length - 1];
    }

    empty() {
        return this.pushStack.length === 0 && this.popStack.length === 0;
    }
}

// Driver code
const q = new MyQueue();
q.push(1);
q.push(2);
console.log(q.peek());  // 1
console.log(q.pop());   // 1
console.log(q.empty()); // false

Line Notes

this.pushStack = []Stack to hold pushed elements before transfer

this.popStack = []Stack to hold elements for popping in queue order

this.pushStack.push(x)Push new element onto push stack efficiently

if (this.popStack.length === 0)Transfer elements only if pop stack is empty to maintain order

while (this.pushStack.length > 0)Move all elements from push to pop stack to reverse order

return this.popStack.pop()Pop front element from pop stack efficiently

return this.popStack[this.popStack.length - 1]Peek front element from pop stack efficiently

return this.pushStack.length === 0 && this.popStack.length === 0Queue empty if both stacks are empty

⏱

Complexity

TimeAmortized O(1) per operation

SpaceO(n) for two stacks

Each element is pushed and popped at most twice, so average time per operation is O(1).

💡 For n=20 operations, total work is about 40 stack operations, very efficient.

Interview Verdict: Accepted and optimal solution

This is the best approach to implement queue using stacks in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the optimal two stacks approach in 95% of interviews for best performance and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (One Stack Recursion)	O(n) per pop/peek	O(n) + recursion stack	Yes (deep recursion)	N/A	Mention only - never code
2. Two Stacks Push Costly	O(n) per push, O(1) pop/peek	O(n)	No	N/A	Good to explain but not optimal
3. Two Stacks Pop Costly (Optimal)	Amortized O(1) per operation	O(n)	No	N/A	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know how to present your solution clearly in interviews.

How to Present

Clarify the problem and confirm queue operations required.Explain the brute force recursive approach to show understanding.Introduce the two stacks approach with costly push.Finally, present the optimal two stacks approach with amortized O(1).Write clean code and test with examples.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your understanding of stack and queue differences, ability to simulate one data structure with another, and knowledge of amortized analysis.

Common Follow-ups

• Can you implement queue using only one stack? → Recursive approach
• What is the amortized time complexity of your solution? → Explain element movement count

💡 These follow-ups check deeper understanding of data structure simulation and complexity analysis.

🔍

Pattern Recognition

When to Use

1) Asked to implement queue using stacks; 2) Need FIFO behavior from LIFO structures; 3) Two stacks available; 4) Amortized efficiency desired.

Signature Phrases

Implement queue using stacksSimulate FIFO with LIFOTwo stacks to implement queue

NOT This Pattern When

Problems that require only normal queue or stack usage without simulation.

Similar Problems

Implement Stack using Queues - inverse problemMin Stack - stack design with extra infoSliding Window Maximum - uses monotonic stacks

Practice

1. You are given a string containing encoded patterns like 3[a2[c]], where numbers indicate how many times the substring inside brackets should be repeated. Which algorithmic approach guarantees an optimal and correct decoding of such nested patterns?

easy

A. Greedy approach that expands the first encountered bracketed substring repeatedly until no brackets remain

B. Simple recursion that decodes substrings without using any auxiliary data structures

C. Dynamic programming approach that builds solutions bottom-up using substring indices

D. Stack-based iterative approach that uses two stacks to track counts and substrings, handling nested patterns correctly

Solution

1. Step 1: Understand nested pattern decoding

   The problem requires handling nested brackets and repeat counts, which demands tracking multiple levels of context.

2. Step 2: Identify approach that handles nesting efficiently

   A stack-based iterative approach uses two stacks to store counts and partial decoded strings, correctly managing nested repeats without excessive recursion or incorrect greedy expansions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Stack approach correctly decodes nested patterns like 3[a2[c]] -> accaccacc [OK]

Hint: Nested repeats require stack to track context [OK]

Common Mistakes:

• Assuming greedy expansion works for nested patterns
• Using recursion without proper state tracking

2. Consider the following Python function that computes the largest rectangle area in a histogram using a monotonic stack approach. Given the input heights = [2, 1, 5], what is the value of the variable right after computing the right boundaries (just before calculating max_area)?

easy

A. [1, 2, 3]

B. [1, 3, 2]

C. [1, 3, 3]

D. [3, 3, 3]

Solution

1. Step 1: Trace right boundary computation for i=2 (height=5)

   Stack is empty, so right[2] = n = 3, stack = [2]

2. Step 2: Trace i=1 (height=1)

   Pop indices with height >= 1: pop 2 (height=5), stack empty, right[1] = 3, stack = [1]

3. Step 3: Trace i=0 (height=2)

   Stack top is 1 (height=1) < 2, so right[0] = 1, stack = [1,0]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Right boundaries correctly reflect next smaller bar indices [OK]

Hint: Right boundaries found by scanning from right with stack [OK]

Common Mistakes:

• Confusing indices or off-by-one in right boundary
• Not clearing stack before right boundary pass

3. What is the time and space complexity of the two-pass counter approach for the longest valid parentheses problem on an input string of length n?

medium

A. Time: O(n log n), Space: O(1) due to sorting-like operations

B. Time: O(n^2), Space: O(n) due to scanning and counters

C. Time: O(n), Space: O(n) because of recursion stack or auxiliary arrays

D. Time: O(n), Space: O(1) because it scans twice with constant counters

Solution

1. Step 1: Identify time complexity of two passes

   The algorithm scans the string twice (left-to-right and right-to-left), each O(n), total O(n).

2. Step 2: Identify space complexity

   Only counters (left, right, max_len) are used, no extra arrays or recursion stack, so O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two linear scans with constant variables confirm O(n) time and O(1) space [OK]

Hint: Two passes with counters use constant space [OK]

Common Mistakes:

• Assuming recursion or DP adds O(n) space
• Confusing scanning with nested loops
• Thinking counters require arrays

4. The following code attempts to solve the Next Greater Element II problem using a monotonic stack and explicit circular array copy. Identify the line containing the subtle bug that causes incorrect results on some inputs.

from typing import List

def nextGreaterElements(nums: List[int]) -> List[int]:
    n = len(nums)
    doubled = nums + nums
    answer = [-1] * n
    stack = []
    for i, num in enumerate(doubled):
        while stack and doubled[stack[-1]] < num:
            idx = stack.pop()
            if idx < n:
                answer[idx] = num
        if i < n:
            stack.append(i)  # Bug here
    return answer

medium

A. Line pushing indices onto stack only when i < n

B. Line popping from stack while top element is less than current num

C. Line initializing answer array with -1

D. Line creating doubled array by concatenation

Solution

1. Step 1: Understand stack push condition

   Only pushing indices when i < n means indices from second pass (i ≥ n) are never pushed, so some elements' next greater values are missed.

2. Step 2: Identify correct push strategy

   To simulate circular array correctly, indices should be pushed for the entire doubled array, or a different approach used. Restricting push to i < n causes missing updates.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bug is in restricting stack pushes to first pass only [OK]

Hint: Pushing indices only in first pass misses circular wrap [OK]

Common Mistakes:

• Not pushing indices in second pass causing incomplete updates
• Using values instead of indices in stack
• Not initializing answer array with -1

5. Consider this buggy code for the stock span problem. Which line contains the subtle bug that causes incorrect spans when prices are equal?

medium

A. Line 9: span calculation does not add 1 when stack is not empty

B. Line 11: appending price after appending index to stack

C. Line 6: while condition uses '<' instead of '<='

D. Line 7: popping from stack without checking if empty

Solution

1. Step 1: Identify the bug in while condition

   The condition uses '<' instead of '<=', so equal prices are not popped, causing incorrect spans.

2. Step 2: Confirm other lines are correct

   Span calculation correctly handles empty stack. Appending order is correct. Stack emptiness is checked before popping.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Using '<=' ensures equal prices are popped for correct spans [OK]

Hint: Use '<=' in while to pop equal or smaller prices [OK]

Common Mistakes:

• Using '<' causes incorrect spans for equal prices
• Misplaced span calculation