Stacks and Queues Master Recap — All Patterns, Templates, and Interview Cheatsheet

Problem Statement#

This is the closing recap for the Stacks and Queues category (problems 251 through 300). After 45 individual posts, this single file consolidates every pattern, template, and decision rule you need on interview day.

Constraints:

• Fit on a single screen for each pattern
• Provide both Python and JavaScript templates
• Sort patterns by interview frequency
• Include trigger phrases for fast recognition

Input:  Any stack/queue problem you have not seen before
Output: Correct pattern in under 60 seconds

Why This Problem Matters#

Most candidates fail stack problems not from lack of knowledge but from lack of speed. Forty-five minutes is not enough to derive a monotonic stack from first principles — you need the template loaded in your fingers. This recap exists so that the night before your interview you can scroll through it once and walk in confident.

The patterns are sorted by how often they appear in real Google, Meta, and Amazon loops based on Glassdoor and LeetCode discuss data through 2026. The top three patterns (monotonic stack, BFS, deque) make up roughly seventy percent of stack and queue questions.

The Core Insight#

Every stack and queue problem reduces to one of seven patterns. Pattern recognition is the entire game. Once you see the trigger phrase, the template writes itself.

Visual Dry Run#

Solution (Optimal)#

Template 1 — Monotonic Decreasing Stack#

def next_greater(nums):
    n = len(nums)
    res = [-1] * n
    stack = []
    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 res = new Array(nums.length).fill(-1);
    const stack = [];
    for (let i = 0; i < nums.length; i++) {
        while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
            res[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return res;
};

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

Template 2 — BFS on Grid#

from collections import deque
 
def bfs(grid, start):
    R, C = len(grid), len(grid[0])
    q = deque([(start, 0)])
    seen = {start}
    while q:
        (r, c), d = q.popleft()
        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 (nr, nc) not in seen and grid[nr][nc] == 0:
                seen.add((nr, nc))
                q.append(((nr, nc), d + 1))
    return -1

var bfs = function(grid, start) {
    const R = grid.length, C = grid[0].length;
    const q = [[start, 0]];
    const seen = new Set([start.join(',')]);
    while (q.length) {
        const [[r, c], d] = q.shift();
        for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
            const nr = r + dr, nc = c + dc;
            const key = nr + ',' + nc;
            if (nr >= 0 && nr < R && nc >= 0 && nc < C && !seen.has(key) && grid[nr][nc] === 0) {
                seen.add(key);
                q.push([[nr, nc], d + 1]);
            }
        }
    }
    return -1;
};

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

Template 3 — Monotonic Deque (Sliding Window Max)#

from collections import deque
 
def max_window(nums, k):
    dq, res = deque(), []
    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 maxWindow = function(nums, k) {
    const dq = [], 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)

Template 4 — Min Stack#

class MinStack:
    def __init__(self):
        self.stack = []
        self.mins = []
    def push(self, x):
        self.stack.append(x)
        self.mins.append(x if not self.mins else min(x, self.mins[-1]))
    def pop(self):
        self.stack.pop()
        self.mins.pop()
    def top(self):
        return self.stack[-1]
    def getMin(self):
        return self.mins[-1]

class MinStack {
    constructor() { this.stack = []; this.mins = []; }
    push(x) {
        this.stack.push(x);
        this.mins.push(this.mins.length ? Math.min(x, this.mins[this.mins.length - 1]) : x);
    }
    pop() { this.stack.pop(); this.mins.pop(); }
    top() { return this.stack[this.stack.length - 1]; }
    getMin() { return this.mins[this.mins.length - 1]; }
}

Time: O(1) per op Space: O(n)

Template 5 — Valid Parentheses#

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in pairs:
            if not stack or stack.pop() != pairs[c]:
                return False
        else:
            stack.append(c)
    return not stack

var isValid = function(s) {
    const pairs = { ')': '(', ']': '[', '}': '{' };
    const stack = [];
    for (const c of s) {
        if (c in pairs) {
            if (!stack.length || stack.pop() !== pairs[c]) return false;
        } else {
            stack.push(c);
        }
    }
    return stack.length === 0;
};

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

Common Mistakes#

• Forgetting to flush the monotonic stack after the loop ends — values that never trigger a pop are left unanswered.
• Using array shift() in JavaScript for BFS — that is O(n). Use a head pointer or a real deque.
• Storing values instead of indices in monotonic stacks. Width calculations need indices.
• In min stack, pushing only when smaller than current min — breaks pop correspondence.
• Reading dq[0] without first sliding the window. Always evict stale indices first.

Interview Tips#

• Open every problem with: "Let me identify the pattern. The phrase X tells me this is Y."
• Write the template first, then adapt. Never write a monotonic stack from scratch under time pressure.
• For BFS questions, always ask: "Are diagonals neighbors?" and "Can I mutate the grid?".
• State amortized analysis explicitly for two-stack queue and monotonic stack — interviewers expect it.
• Practice the dry-run table format. Drawing it on the whiteboard impresses interviewers.

Follow-up Questions#

• "Can you solve Largest Rectangle in O(1) extra space?" — No, but you can do it with one pass instead of two.
• "What changes if duplicates are allowed?" — In Sum of Subarray Minimums, use strict-less on one side and non-strict on the other to avoid double counting.
• "Implement a queue using two stacks with amortized O(1) ops." — Push to in-stack, transfer to out-stack on demand.
• "How do you find the next greater for each in a circular array?" — Iterate 2n indices modulo n.
• "Can BFS be done bidirectionally?" — Yes, expand from both ends and meet in the middle.

Key Takeaways#

• Seven patterns cover the entire Stacks and Queues category.
• Monotonic stacks store indices, run in amortized O(n), and solve all next-greater problems.
• BFS is the unweighted shortest path tool — always pair it with a deque, never shift().
• A monotonic deque is the only optimal way to do sliding window max or min.
• Two-stack tricks turn O(n) min queries into O(1) at the cost of O(n) space.
• Bracket and expression problems are stack-of-state problems — name the state explicitly.
• Memorize templates, recognize triggers, and never derive from scratch in an interview.