Stacks and Queues Complete Guide — All Patterns and Problem Index for FAANG Interviews

Problem Statement#

This is the master guide for the entire Stacks and Queues category covering 50 problems numbered 251 through 300. The goal is simple: given any stack or queue interview question, you should be able to identify the pattern, recall the template, and finish coding in under 15 minutes.

Constraints:

• Cover all seven core patterns
• Provide working Python and JavaScript templates
• Map each pattern to canonical LeetCode problems
• Stay under 350 lines so it loads fast on mobile

Input:  Any stack/queue interview question
Output: Pattern name + template + Big-O analysis

Why This Problem Matters#

Stacks and queues are the highest-yield interview topic per hour of study. A monotonic stack alone unlocks Daily Temperatures, Next Greater Element I/II/III/IV, Largest Rectangle in Histogram, Trapping Rain Water, Sum of Subarray Minimums, and Stock Span — six problems that appear in roughly forty percent of Google and Amazon onsite loops.

The reason is mechanical. Stack problems compress to a single template (push index, pop while condition, settle answer on pop). Once you internalize that template, you stop thinking and start writing. Interviewers know this and use these problems as a calibration signal — if you fumble the monotonic stack template, they assume you have not done the prep work.

This guide collects every template you need, ranked by interview frequency. The patterns are listed in the order you should learn them.

The Core Insight#

Stack problems are about "the next/previous element with property X". Queue problems are about "shortest path in unweighted graph" or "order preservation". Deque problems are the union: "sliding window extremum" needs both ends.

Three diagnostic questions answer ninety percent of these problems:

1. Are you scanning for the nearest element on the left or right with some comparison? Use a monotonic stack.
2. Are you exploring layer by layer from a source? Use BFS with a queue.
3. Do you need both the front and back of a window? Use a deque.

Visual Dry Run#

Solution (Optimal)#

Pattern 1 — Monotonic Decreasing Stack (Next Greater)#

def next_greater(nums):
    n = len(nums)
    res = [-1] * n
    stack = []  # stores indices
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            res[stack.pop()] = nums[i]
        stack.append(i)
    return res

var nextGreater = function(nums) {
    const n = nums.length;
    const res = new Array(n).fill(-1);
    const stack = [];
    for (let i = 0; i < n; i++) {
        while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
            res[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return res;
};

Time: O(n) amortized — each index is pushed and popped at most once. Space: O(n) for the stack.

Pattern 2 — Monotonic Increasing Stack (Largest Rectangle)#

def largest_rectangle(heights):
    heights = [0] + heights + [0]
    stack = [0]
    ans = 0
    for i in range(1, len(heights)):
        while heights[stack[-1]] > heights[i]:
            h = heights[stack.pop()]
            w = i - stack[-1] - 1
            ans = max(ans, h * w)
        stack.append(i)
    return ans

var largestRectangle = function(heights) {
    heights = [0, ...heights, 0];
    const stack = [0];
    let ans = 0;
    for (let i = 1; i < heights.length; i++) {
        while (heights[stack[stack.length - 1]] > heights[i]) {
            const h = heights[stack.pop()];
            const w = i - stack[stack.length - 1] - 1;
            ans = Math.max(ans, h * w);
        }
        stack.push(i);
    }
    return ans;
};

Time: O(n) Space: O(n)

Pattern 3 — BFS Multi-Source (Rotting Oranges)#

from collections import deque
 
def oranges_rotting(grid):
    R, C = len(grid), len(grid[0])
    q = deque()
    fresh = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 2:
                q.append((r, c, 0))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while q:
        r, c, t = q.popleft()
        minutes = t
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh -= 1
                q.append((nr, nc, t + 1))
    return minutes if fresh == 0 else -1

var orangesRotting = function(grid) {
    const R = grid.length, C = grid[0].length;
    const q = [];
    let fresh = 0;
    for (let r = 0; r < R; r++)
        for (let c = 0; c < C; c++) {
            if (grid[r][c] === 2) q.push([r, c, 0]);
            else if (grid[r][c] === 1) fresh++;
        }
    let minutes = 0;
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    while (q.length) {
        const [r, c, t] = q.shift();
        minutes = t;
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === 1) {
                grid[nr][nc] = 2;
                fresh--;
                q.push([nr, nc, t + 1]);
            }
        }
    }
    return fresh === 0 ? minutes : -1;
};

Time: O(R * C) Space: O(R * C)

Pattern 4 — Monotonic Deque (Sliding Window Max)#

from collections import deque
 
def max_sliding_window(nums, k):
    dq = deque()  # stores indices, values decreasing
    res = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] < x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

var maxSlidingWindow = function(nums, k) {
    const dq = [];
    const res = [];
    for (let i = 0; i < nums.length; i++) {
        while (dq.length && nums[dq[dq.length - 1]] < nums[i]) dq.pop();
        dq.push(i);
        if (dq[0] <= i - k) dq.shift();
        if (i >= k - 1) res.push(nums[dq[0]]);
    }
    return res;
};

Time: O(n) Space: O(k)

Common Mistakes#

• Storing values instead of indices in monotonic stacks. You almost always need the index for width calculations.
• Using strict less-than when equal-to handling matters (Sum of Subarray Minimums needs careful tie-breaking).
• Forgetting to flush the stack after the main loop in problems like Trapping Rain Water.
• Using a Python list as a queue with pop(0) — that is O(n). Use collections.deque.
• In BFS, marking cells as visited only after popping (causes duplicate enqueues). Mark on enqueue.

Interview Tips#

• State the pattern out loud before coding: "This is a next-greater problem, so I'll use a monotonic decreasing stack of indices."
• Walk through one concrete example before writing code. Interviewers gauge clarity from this step.
• For BFS, always confirm with the interviewer whether diagonals count as neighbors.
• When using two stacks for a queue, mention the amortized O(1) analysis — it scores points.

Follow-up Questions#

• "What if the array is circular?" — Iterate twice modulo n (Next Greater Element II pattern).
• "What if you need the previous greater instead?" — Reverse iteration or flip the comparison.
• "Can you do sliding window minimum with the same deque?" — Yes, flip the comparison to keep increasing.
• "What if k changes per query?" — Sparse table or segment tree, not deque.
• "How would you parallelize BFS?" — Frontier expansion with thread-local queues, merge per layer.

Key Takeaways#

• Seven patterns cover every stack and queue problem you will see in interviews.
• Monotonic stacks always store indices and are amortized O(n).
• BFS with a deque is the default for shortest-path on unweighted grids and graphs.
• Use a monotonic deque whenever a sliding window asks for max or min.
• Two-stack tricks turn O(n) operations into amortized O(1).
• Bracket and expression problems are stack-of-state problems — define the state carefully.
• Master the templates first, then practice trigger-phrase recognition until it is reflexive.