CoursesFeatured DecksInterview ExperiencesTop Interview QuestionsExploreBlog
← Back to Course

Top Interview Questions for Stacks and Queues

Stack & Queue Interview Problem Variants

Stack & Queue Problem Variants

Frequently Asked in Coding Interviews

Introduction

Coding interview questions often reuse common stack and queue patterns. Below, we highlight some of the most frequently appearing variants from LeetCode, each illustrating a key concept or twist. We organize them into stack-based and queue-based problems, and for each variant we provide the unique tweak to the base template, an example problem, a step-by-step walkthrough, and solution code when the pattern deviates significantly from the basics.

Stack Variants

Balanced Parentheses (Stack for Matching Pairs)

Modified Template: Use a stack to track opening brackets. Push opening symbols; for every closing symbol, pop and check if it matches the expected type. The tweak is a conditional pop based on matching types. At the end, the stack must be empty.

Example Problem: LeetCode 20 – Valid Parentheses. Given s = "()[]{}", determine if valid.

One Full Walkthrough (s = "{[()]}"):
  1. Read {. Push {. Stack: [{].
  2. Read [. Push [. Stack: [{, [].
  3. Read (. Push (. Stack: [{, [, (].
  4. Read ). Top is (, matches. Pop. Stack: [{, [].
  5. Read ]. Top is [, matches. Pop. Stack: [{].
  6. Read }. Top is {, matches. Pop. Stack: [] (empty).
Result: Valid. 
def isValid(s: str) -> bool:
    bracket_map = {')':'(', '}':'{', ']':'['}
    stack = []
    for char in s:
        if char in '([{':
            stack.append(char)
        else: # closing bracket
            if not stack or stack[-1] != bracket_map[char]:
                return False
            stack.pop()
    return not stack

Monotonic Stack (Next Greater Element / Daily Temperatures)

Modified Template: Maintain a monotonic (usually decreasing) stack of values or indices. Pop from stack when a new element breaks the monotonic property (e.g., new element is greater). This finds the "next greater" element for popped items.

Example Problem: LeetCode 739 – Daily Temperatures. Find days until a warmer temperature.

One Full Walkthrough (temps = [73, 74, 71, 69, 72, 76]):
  1. Day 0 (73): Stack empty, push 0. Stack: [0]. Answer: [0,0,0,0,0,0].
  2. Day 1 (74): 74 > 73. Pop 0. answer[0]=1-0=1. Push 1. Stack: [1]. Answer: [1,0,0,0,0,0].
  3. Day 2 (71): 71 < 74. Push 2. Stack: [1,2].
  4. Day 3 (69): 69 < 71. Push 3. Stack: [1,2,3].
  5. Day 4 (72): 72 > 69. Pop 3. answer[3]=4-3=1. 72 > 71. Pop 2. answer[2]=4-2=2. 72 < 74. Push 4. Stack: [1,4]. Answer: [1,0,2,1,0,0].
  6. Day 5 (76): 76 > 72. Pop 4. answer[4]=5-4=1. 76 > 74. Pop 1. answer[1]=5-1=4. Push 5. Stack: [5]. Answer: [1,4,2,1,1,0].
End: Index 5 remains, answer[5]=0. Final: [1,4,2,1,1,0]. 
def dailyTemperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = [] # stores indices
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

Min Stack (Stack with Constant-Time Min Tracking)

Modified Template: Design a stack supporting push, pop, top, and getMin() in O(1) time. Maintain an auxiliary stack (or store min with each element) to track the current minimum.

Example Problem: LeetCode 155 – Min Stack.

One Full Walkthrough:
  1. init(): stack=[], min_stack=[]
  2. push(5): stack=[5], min_stack=[5] (min=5)
  3. push(2): stack=[5,2], min_stack=[5,2] (min=2)
  4. push(7): stack=[5,2,7], min_stack=[5,2,2] (min=2, as 7>2)
  5. getMin(): returns top of min_stack (2)
  6. pop(): pops 7 from stack, 2 from min_stack. stack=[5,2], min_stack=[5,2] (min=2)
  7. pop(): pops 2 from stack, 2 from min_stack. stack=[5], min_stack=[5] (min=5)
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    def push(self, x: int):
        self.stack.append(x)
        if not self.min_stack: self.min_stack.append(x)
        else: self.min_stack.append(min(x, self.min_stack[-1]))
    def pop(self):
        self.stack.pop()
        self.min_stack.pop()
    def top(self) -> int: return self.stack[-1]
    def getMin(self) -> int: return self.min_stack[-1]

Largest Rectangle in Histogram

Modified Template: Use a monotonic increasing stack of bar indices. Pop when a lower bar is met, calculating area for the popped bar. Append a zero-height bar at end to flush stack.

Example Problem: LeetCode 84 – Largest Rectangle in Histogram.

One Full Walkthrough (h = [2,1,5,6,2,3], append 0):
  1. idx 0 (h=2): Stack empty, push 0. Stack:[0]. MaxArea=0.
  2. idx 1 (h=1): 1 < h[0]=2. Pop 0. width=1. area=2*1=2. MaxArea=2. Push 1. Stack:[1].
  3. idx 2 (h=5): 5 > h[1]=1. Push 2. Stack:[1,2].
  4. idx 3 (h=6): 6 > h[2]=5. Push 3. Stack:[1,2,3].
  5. idx 4 (h=2): 2 < h[3]=6. Pop 3. height=6, width=4-2-1=1. area=6. MaxArea=6.
    Now 2 < h[2]=5. Pop 2. height=5, width=4-1-1=2. area=10. MaxArea=10.
    2 > h[1]=1. Push 4. Stack:[1,4].
  6. idx 5 (h=3): 3 > h[4]=2. Push 5. Stack:[1,4,5].
  7. idx 6 (h=0, sentinel): 0 < h[5]=3. Pop 5. height=3, width=6-4-1=1. area=3. MaxArea=10.
    0 < h[4]=2. Pop 4. height=2, width=6-1-1=4. area=8. MaxArea=10.
    0 < h[1]=1. Pop 1. height=1, width=6-(-1)-1=6. area=6. MaxArea=10.
    Push 6. Stack:[6].
Result: MaxArea = 10. 
def largestRectangleArea(heights: list[int]) -> int:
    stack = [] # indices
    max_area = 0
    for i, h in enumerate(heights + [0]):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            left_idx = stack[-1] if stack else -1
            width = i - left_idx - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

Queue Variants

BFS on Matrix/Grid (Multi-source BFS – Rotting Oranges)

Modified Template: Use BFS queue over a matrix, often from multiple sources. Initialize queue with all starting points (e.g., rotten oranges). Process in waves (levels) to simulate spread by time steps.

Example Problem: LeetCode 994 – Rotting Oranges. Grid with fresh(1)/rotten(2)/empty(0) oranges. Rotten oranges infect adjacent fresh ones per minute. Find min minutes until no fresh remain.

One Full Walkthrough (Grid: [[2,1,1],[1,1,0],[0,1,1]]):
  1. Min 0: Queue=[(0,0)]. Fresh=6. (Corrected fresh count: (0,1),(0,2),(1,0),(1,1),(2,1),(2,2)).
  2. Min 1: Process (0,0). Rots (0,1), (1,0). Fresh=4. Queue for next: [(0,1), (1,0)].
  3. Min 2: Process (0,1) -> rots (0,2), (1,1). Process (1,0) -> (no new fresh neighbors already considered from (0,1)). Fresh=2. Queue for next: [(0,2), (1,1)].
  4. Min 3: Process (0,2) -> no new fresh. Process (1,1) -> rots (2,1). Fresh=1. Queue for next: [(2,1)].
  5. Min 4: Process (2,1) -> rots (2,2). Fresh=0. Queue for next: [(2,2)].
All fresh rotten in 4 minutes. 
from collections import deque
def orangesRotting(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    q = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2: q.append((r, c))
            elif grid[r][c] == 1: fresh += 1
    
    minutes = 0
    directions = [(1,0),(-1,0),(0,1),(0,-1)]
    
    while q and fresh > 0:
        for _ in range(len(q)): # Process one level (minute)
            x, y = q.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:
                    grid[nx][ny] = 2
                    fresh -= 1
                    q.append((nx, ny))
        minutes += 1
    return minutes if fresh == 0 else -1

Monotonic Queue (Sliding Window Maximum)

Modified Template: Use a deque to maintain window elements (indices) in decreasing order of their values. Pop from front when element exits window; pop from back any elements smaller than the new one (as they can't be max). Deque's front is always current window max.

Example Problem: LeetCode 239 – Sliding Window Maximum. Given array and window size k, output max in each window.

One Full Walkthrough (nums=[1,3,-1,-3,5,3,6,7], k=3):
  1. Win [1,3,-1] (idx 0-2): Deque: Push 0 (1). Pop 0, Push 1 (3). Push 2 (-1). Deque:[1,2]. Max: nums[1]=3. Result:[3].
  2. Win [3,-1,-3] (idx 1-3): Check dq[0]=1 (in window). Add nums[3]=-3. Deque:[1,2,3]. Max: nums[1]=3. Result:[3,3].
  3. Win [-1,-3,5] (idx 2-4): dq[0]=1 (out of window [2,4]), pop 1. Deque:[2,3]. Add nums[4]=5. Pop 3 (-3<5), Pop 2 (-1<5). Push 4. Deque:[4]. Max: nums[4]=5. Result:[3,3,5].
  4. ...and so on. Final Result: [3,3,5,5,6,7].
from collections import deque
def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    dq = deque() # stores indices
    result = []
    for i, value in enumerate(nums):
        # Remove indices out of window
        if dq and dq[0] < i - k + 1: dq.popleft()
        # Remove smaller values from back
        while dq and nums[dq[-1]] < value: dq.pop()
        dq.append(i)
        if i >= k - 1: result.append(nums[dq[0]])
    return result

Design: Implement Queue using Stacks

Modified Template: Use two stacks (in-stack, out-stack) to emulate FIFO queue. Push to in-stack. For pop/peek, if out-stack empty, pour all from in-stack to out-stack (reverses order).

Example Problem: LeetCode 232 – Implement Queue using Stacks.

One Full Walkthrough:
  1. init(): in_stk=[], out_stk=[]
  2. push(1): in_stk=[1]
  3. push(2): in_stk=[1,2]
  4. peek(): out_stk empty. Pour: out_stk=[2,1], in_stk=[]. Returns out_stk.top (1).
  5. pop(): out_stk not empty. Pops 1. out_stk=[2].
  6. empty(): False (out_stk has 2).
class MyQueue:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []
    def push(self, x: int): self.stack_in.append(x)
    def _transfer_if_needed(self):
        if not self.stack_out:
            while self.stack_in: self.stack_out.append(self.stack_in.pop())
    def pop(self) -> int:
        self._transfer_if_needed()
        return self.stack_out.pop()
    def peek(self) -> int:
        self._transfer_if_needed()
        return self.stack_out[-1]
    def empty(self) -> bool: return not self.stack_in and not self.stack_out

Time-Based Sliding Window (Recent Calls Counter)

Modified Template: Use a queue for items within a time window (timestamps). Enqueue new events; dequeue old events outside the time frame from queue front upon query.

Example Problem: LeetCode 933 – Number of Recent Calls. ping(t) returns calls in last 3000ms.

One Full Walkthrough:
  1. RecentCounter(): q=[]
  2. ping(1): Add 1. q=[1]. Remove calls < 1-3000 (none). Return len(q)=1.
  3. ping(100): Add 100. q=[1,100]. Remove calls < 100-3000 (none). Return len(q)=2.
  4. ping(3001): Add 3001. q=[1,100,3001]. Remove calls < 3001-3000=1 (none, 1 is not < 1). Return len(q)=3.
  5. ping(3002): Add 3002. q=[1,100,3001,3002]. Remove calls < 3002-3000=2. Pop 1. q=[100,3001,3002]. Return len(q)=3.
from collections import deque
class RecentCounter:
    def __init__(self): self.q = deque()
    def ping(self, t: int) -> int:
        self.q.append(t)
        while self.q and self.q[0] < t - 3000: self.q.popleft()
        return len(self.q)

Interactive Animations

{[()]}Stack:
Stack: []

Input string for Balanced Parentheses.

© Stack & Queue Variants Explained. Content adapted for educational purposes.

We use cookies to improve your experience. By clicking “Accept” you consent to the use of cookies. Read our Privacy Policy.