Stacks and queues. Two of the first data structures you learn. So simple that most tutorials spend about five minutes on them before moving on to "the real stuff." Push, pop, enqueue, dequeue. Easy. Next topic. And then you sit down for a coding interview, someone asks you to find the next greater element for every item in an array, and you stare at the screen thinking, "How is a stack supposed to help me here?" Here's the thing about stacks and queues: **the data structures themselves are trivial**. An array can be a stack. An array can be a queue. There's nothing complicated about the mechanics. But the *patterns* they unlock — matching nested structures, tracking running minimums, finding next-greater relationships, processing levels, optimizing sliding windows — these are among the most commonly tested patterns in coding interviews. And they're elegant once you see them. The gap isn't understanding how a stack works. The gap is knowing *when to reach for one*. That's what this guide is about. > The data structure is simple. The insight is what matters. This guide is about building that insight. We're going to work through every major stack and queue pattern you'll encounter in interviews, from the warm-up classics to the boss battles. Each problem gets a full TypeScript solution, a step-by-step walkthrough, and a breakdown of *why* the approach works — not just *what* the code does. By the end, you'll have a mental framework for recognizing when a stack or queue is the right tool for the job. Let's get into it. --- ## The Big Idea: Stacks Keep Context, Queues Keep Order Before we dive into problems, let's build the right mental model. A **stack** is Last-In, First-Out (LIFO). The most recently added item is the first one you access. Think of a stack of plates: you always grab the top one. A **queue** is First-In, First-Out (FIFO). The first item added is the first one you access. Think of a line at a coffee shop: first come, first served. But here's the deeper insight that separates beginners from people who crush these problems: - **Stacks maintain "most recent" context.** They're your go-to when you need to remember what you saw recently and match it against what you're seeing now. Nested brackets? Most recent opening bracket. Undo operations? Most recent action. Expression evaluation? Most recent operand. - **Queues maintain order and levels.** They're your go-to when you need to process things in the order they arrived, or when you need to work through something level by level. BFS traversal? Process nodes in discovery order. Sliding windows? Maintain elements in arrival order. > **When to think "stack"**: The problem involves nesting, matching, most-recent context, or "next greater/smaller" relationships. > > **When to think "queue"**: The problem involves ordering, levels, FIFO processing, or sliding windows. Keep these heuristics in the back of your mind as we work through problems. You'll start to feel when each one applies. --- ## Stack Pattern #1: Valid Parentheses (LeetCode 20) This is *the* classic stack problem. If stacks had a mascot, this would be it. It's the problem that makes the stack data structure click for most people. ### Problem > Given a string `s` containing just the characters `(`, `)`, `{`, `}`, `[` and `]`, determine if the input string is valid. An input string is valid if: > 1. Open brackets are closed by the same type of brackets. > 2. Open brackets are closed in the correct order. > 3. Every close bracket has a corresponding open bracket of the same type. ### Examples ``` Input: s = "()" → Output: true Input: s = "()[]{}" → Output: true Input: s = "(]" → Output: false Input: s = "([)]" → Output: false Input: s = "{[]}" → Output: true ``` ### The Key Insight When you encounter a closing bracket, you need to check if it matches the **most recently seen** unmatched opening bracket. "Most recently seen" — that's stack territory. Push every opening bracket onto the stack. When you hit a closing bracket, pop from the stack and check if it's the matching opener. ### TypeScript Solution ```typescript function isValid(s: string): boolean { const stack: string[] = []; const pairs: Record = { ')': '(', '}': '{', ']': '[', }; for (const char of s) { if (char === '(' || char === '{' || char === '[') { stack.push(char); } else { if (stack.length === 0 || stack[stack.length - 1] !== pairs[char]) { return false; } stack.pop(); } } return stack.length === 0; } ``` ### Step-by-Step Walkthrough Let's trace through `s = "{[]}"`: ``` char = '{' → opening bracket → push → stack: ['{'] char = '[' → opening bracket → push → stack: ['{', '['] char = ']' → closing bracket → peek: '[' matches pairs[']'] = '[' ✅ → pop → stack: ['{'] char = '}' → closing bracket → peek: '{' matches pairs['}'] = '{' ✅ → pop → stack: [] End: stack is empty → return true ✅ ``` Now let's trace `s = "([)]"`: ``` char = '(' → push → stack: ['('] char = '[' → push → stack: ['(', '['] char = ')' → closing bracket → peek: '[' !== pairs[')'] = '(' ❌ → return false ``` The brackets are *all present* but in the wrong nesting order. The stack catches this instantly. ### Why This Works The stack naturally tracks the nesting structure. Every opening bracket gets pushed, creating a "to-do list" of brackets that need closing. When a closing bracket appears, it must match the top of the stack — the most recent unclosed opener. If it doesn't match, or if the stack is empty when we need to pop, the string is invalid. > This is the fundamental stack pattern: **use a stack to track open/pending items, and resolve them in reverse order (most recent first).** ### Complexity | Metric | Complexity | |--------|-----------| | Time | O(n) — single pass through the string | | Space | O(n) — worst case, all opening brackets | --- ## Stack Pattern #2: Min Stack (LeetCode 155) This problem seems like it should be impossible — but it's actually a beautiful trick. ### Problem > Design a stack that supports push, pop, top, and retrieving the minimum element in **constant time** O(1). > - `push(val)` — pushes the element onto the stack. > - `pop()` — removes the element on the top. > - `top()` — gets the top element. > - `getMin()` — retrieves the minimum element in the stack. ### The Challenge Push, pop, and top are trivially O(1) on a stack. The trick is `getMin()`. Normally, finding the minimum of a collection is O(n) — you have to scan everything. How do we get it in O(1)? ### The Key Insight Here's the trick: **at every level of the stack, the minimum can only change when we push or pop**. So what if we store the current minimum *alongside each element*? When we push, we compute the new min (either the value itself or the previous min, whichever is smaller) and store it. When we pop, the previous min is automatically restored because it was stored with the element below. ### TypeScript Solution ```typescript class MinStack { private stack: Array<{ val: number; min: number }> = []; push(val: number): void { const currentMin = this.stack.length === 0 ? val : Math.min(val, this.stack[this.stack.length - 1].min); this.stack.push({ val, min: currentMin }); } pop(): void { this.stack.pop(); } top(): number { return this.stack[this.stack.length - 1].val; } getMin(): number { return this.stack[this.stack.length - 1].min; } } ``` ### Step-by-Step Walkthrough ``` push(-2) → stack: [{ val: -2, min: -2 }] push(0) → min(0, -2) = -2 → stack: [{ val: -2, min: -2 }, { val: 0, min: -2 }] push(-3) → min(-3, -2) = -3 → stack: [..., { val: -3, min: -3 }] getMin() → peek top → min = -3 ✅ pop() → remove { val: -3, min: -3 } → stack: [{ val: -2, min: -2 }, { val: 0, min: -2 }] top() → 0 ✅ getMin() → peek top → min = -2 ✅ (the -3 is gone, min automatically restored) ``` See how the minimum "rewinds" when we pop? That's because each element remembers what the minimum was when it was pushed. No recalculation needed. ### Alternative: Two-Stack Approach Some people prefer using a parallel min stack. The idea is the same, just organized differently: ```typescript class MinStack { private stack: number[] = []; private minStack: number[] = []; push(val: number): void { this.stack.push(val); const currentMin = this.minStack.length === 0 ? val : Math.min(val, this.minStack[this.minStack.length - 1]); this.minStack.push(currentMin); } pop(): void { this.stack.pop(); this.minStack.pop(); } top(): number { return this.stack[this.stack.length - 1]; } getMin(): number { return this.minStack[this.minStack.length - 1]; } } ``` Both approaches have identical complexity. The single-stack version is more compact; the two-stack version can be slightly more space-efficient if you only push to the min stack when a new minimum is encountered (though that adds complexity to `pop`). > The key takeaway: sometimes you can achieve O(1) access by **caching derived values alongside your data**. This pattern of "augmenting" a data structure appears everywhere in algorithm design. ### Complexity | Metric | Complexity | |--------|-----------| | Time | O(1) for all operations | | Space | O(n) for the stack | --- ## Stack Pattern #3: Evaluate Reverse Polish Notation (LeetCode 150) This problem is a great example of how stacks naturally model expression evaluation. ### Problem > You are given an array of strings `tokens` that represents an arithmetic expression in **Reverse Polish Notation** (postfix notation). Evaluate the expression and return the result. > > Valid operators are `+`, `-`, `*`, `/`. Each operand may be an integer or another expression. Division truncates toward zero. ### Example ``` Input: tokens = ["2","1","+","3","*"] Output: 9 Explanation: ((2 + 1) * 3) = 9 ``` ### The Key Insight In Reverse Polish Notation, the operator comes *after* its operands. So when you see a number, you don't know what to do with it yet — just save it. When you see an operator, grab the two most recent numbers and apply it. "Most recent" → stack. ### TypeScript Solution ```typescript function evalRPN(tokens: string[]): number { const stack: number[] = []; const operators = new Set(['+', '-', '*', '/']); for (const token of tokens) { if (operators.has(token)) { const b = stack.pop()!; const a = stack.pop()!; switch (token) { case '+': stack.push(a + b); break; case '-': stack.push(a - b); break; case '*': stack.push(a * b); break; case '/': stack.push(Math.trunc(a / b)); break; } } else { stack.push(Number(token)); } } return stack[0]; } ``` ### Step-by-Step Walkthrough For `tokens = ["2", "1", "+", "3", "*"]`: ``` "2" → number → push → stack: [2] "1" → number → push → stack: [2, 1] "+" → operator → pop 1 (b), pop 2 (a) → 2 + 1 = 3 → push → stack: [3] "3" → number → push → stack: [3, 3] "*" → operator → pop 3 (b), pop 3 (a) → 3 * 3 = 9 → push → stack: [9] Result: 9 ✅ ``` ### Watch the Order Notice we pop `b` first, then `a`. This matters for subtraction and division: `a - b` and `a / b`, where `a` is the *first* operand (pushed earlier, so it's deeper in the stack). Getting this backwards is a classic bug. Also note `Math.trunc` for division — the problem says truncate toward zero, not floor. `Math.trunc(-7 / 2) = -3`, but `Math.floor(-7 / 2) = -4`. That difference matters. ### Complexity | Metric | Complexity | |--------|-----------| | Time | O(n) — single pass | | Space | O(n) — stack stores operands | --- ## Stack Pattern #4: Simplify Path (LeetCode 71) This is a stack problem wearing a string manipulation disguise. ### Problem > Given an absolute Unix-style file path, simplify it. The rules: > - `.` refers to the current directory > - `..` moves up one directory > - Multiple consecutive slashes `//` are treated as a single slash > - The simplified path must start with `/` and not end with `/` ### Examples ``` Input: "/home/" → Output: "/home" Input: "/home//foo/" → Output: "/home/foo" Input: "/home/user/Documents/../Pictures" → Output: "/home/user/Pictures" Input: "/../" → Output: "/" Input: "/home/../../../.." → Output: "/" ``` ### The Key Insight Split the path by `/`. Process each component: - Empty string or `"."` → skip - `".."` → go up one directory (pop from stack) - Anything else → go into that directory (push to stack) Going "up" a directory means undoing the most recent directory entry — that's a stack pop. ### TypeScript Solution ```typescript function simplifyPath(path: string): string { const stack: string[] = []; const parts = path.split('/'); for (const part of parts) { if (part === '' || part === '.') { continue; } else if (part === '..') { stack.pop(); } else { stack.push(part); } } return '/' + stack.join('/'); } ``` ### Step-by-Step Walkthrough For `path = "/home/user/Documents/../Pictures"`: ``` Split by '/': ["", "home", "user", "Documents", "..", "Pictures"] "" → skip "home" → push → stack: ["home"] "user" → push → stack: ["home", "user"] "Documents" → push → stack: ["home", "user", "Documents"] ".." → pop → stack: ["home", "user"] "Pictures" → push → stack: ["home", "user", "Pictures"] Result: "/" + "home/user/Pictures" = "/home/user/Pictures" ✅ ``` > The stack here represents the current directory hierarchy. Each push goes deeper, each pop goes up. Clean and intuitive. ### Complexity | Metric | Complexity | |--------|-----------| | Time | O(n) — split + single pass | | Space | O(n) — stack stores directory names | --- ## The Monotonic Stack: Your New Best Friend Alright, we've warmed up. Now it's time for the pattern that separates "I can use a stack" from "I *think* in stacks." The **monotonic stack** is one of the most powerful and frequently tested stack patterns in coding interviews. It's behind a surprising number of medium and hard problems. ### What Is a Monotonic Stack? A **monotonic stack** is simply a stack where the elements are always in sorted order — either always increasing from bottom to top, or always decreasing. When a new element would violate the order, you pop elements until the order is restored. - **Monotonic decreasing stack** (bottom to top): Elements get smaller. When you encounter a larger element, you pop smaller ones. Used for finding the **next greater element**. - **Monotonic increasing stack** (bottom to top): Elements get smaller going up... wait, that's confusing. Let me clarify. Actually, the naming conventions vary across resources, so let's just focus on the behavior: > **For "next greater element" problems**: Maintain a stack where you pop elements that are *smaller* than the current element. Those popped elements just found their next greater element — it's the current element. > > **For "next smaller element" problems**: Maintain a stack where you pop elements that are *larger* than the current element. Those popped elements just found their next smaller element. The general idea: instead of brute-forcing through every pair looking for relationships, the stack lets us efficiently match each element with its "answer" in a single pass. ### The General Template Here's the monotonic stack template for "next greater element" patterns: ```typescript function monotonicStackTemplate(nums: number[]): number[] { const n = nums.length; const result = new Array(n).fill(-1); const stack: number[] = []; // stores indices for (let i = 0; i < n; i++) { while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) { const idx = stack.pop()!; result[idx] = nums[i]; // nums[i] is the next greater element for nums[idx] } stack.push(i); } return result; } ``` Key points: 1. The stack stores **indices**, not values. This lets us write the answer to the correct position in the result array. 2. Elements remaining in the stack at the end have no next greater element (default -1). 3. Each element is pushed and popped **at most once** → O(n) total, not O(n²). > The magic of the monotonic stack: even though there's a `while` loop inside a `for` loop, the total work is O(n) because each element enters and leaves the stack at most once. This is an **amortized** analysis. Let's see this pattern in action across several classic problems. --- ## Stack Pattern #5: Next Greater Element I (LeetCode 496) ### Problem > You are given two distinct 0-indexed integer arrays `nums1` and `nums2`, where `nums1` is a subset of `nums2`. For each element in `nums1`, find the next greater element in `nums2`. The next greater element of `nums1[i]` is the first element in `nums2` to the right of `nums2[j]` (where `nums2[j] === nums1[i]`) that is greater than `nums2[j]`. If no such element exists, return -1. ### Example ``` Input: nums1 = [4,1,2], nums2 = [1,3,4,2] Output: [-1,3,-1] Explanation: - 4 is at index 2 in nums2. No greater element to its right → -1 - 1 is at index 0 in nums2. Next greater to its right: 3 - 2 is at index 3 in nums2. No greater element to its right → -1 ``` ### The Key Insight Process `nums2` with a monotonic stack to build a map: for every element, what's its next greater element? Then just look up each element from `nums1` in the map. ### TypeScript Solution ```typescript function nextGreaterElement(nums1: number[], nums2: number[]): number[] { const nextGreater = new Map(); const stack: number[] = []; for (const num of nums2) { while (stack.length > 0 && stack[stack.length - 1] < num) { nextGreater.set(stack.pop()!, num); } stack.push(num); } return nums1.map(num => nextGreater.get(num) ?? -1); } ``` ### Step-by-Step Walkthrough For `nums2 = [1, 3, 4, 2]`: ``` num = 1 → stack empty, push → stack: [1] num = 3 → 3 > 1 → pop 1, set nextGreater[1] = 3 → push 3 → stack: [3] num = 4 → 4 > 3 → pop 3, set nextGreater[3] = 4 → push 4 → stack: [4] num = 2 → 2 < 4 → just push → stack: [4, 2] Remaining in stack: 4, 2 → no next greater element (default -1) Map: { 1 → 3, 3 → 4 } nums1 = [4, 1, 2]: 4 → not in map → -1 1 → map[1] = 3 2 → not in map → -1 Result: [-1, 3, -1] ✅ ``` ### Complexity | Metric | Complexity | |--------|-----------| | Time | O(n + m) — process nums2, then look up nums1 | | Space | O(n) — stack + map for nums2 | --- ## Stack Pattern #6: Next Greater Element II (LeetCode 503) Now the twist: the array is **circular**. ### Problem > Given a circular integer array `nums`, return the next greater element for every element. The next greater element of `nums[i]` is the first greater number in the circular traversal starting from `nums[i]`. If no such element exists, return -1. ### Example ``` Input: nums = [1, 2, 1] Output: [2, -1, 2] Explanation: - nums[0] = 1 → next greater is 2 - nums[1] = 2 → wrapping around: 1, 1 — nothing greater → -1 - nums[2] = 1 → wrapping around: 1, 2 — next greater is 2 ``` ### The Key Insight Circular array? **Iterate twice.** By going through the array twice (using modulo arithmetic), every element gets a chance to "look ahead" past the end of the array. Use the same monotonic stack pattern, but only assign results for indices in the first pass (since those are the real indices). ### TypeScript Solution ```typescript function nextGreaterElements(nums: number[]): number[] { const n = nums.length; const result = new Array(n).fill(-1); const stack: number[] = []; for (let i = 0; i < 2 * n; i++) { const current = nums[i % n]; while (stack.length > 0 && nums[stack[stack.length - 1]] < current) { const idx = stack.pop()!; result[idx] = current; } if (i < n) { stack.push(i); } } return result; } ``` ### Step-by-Step Walkthrough For `nums = [1, 2, 1]`: ``` --- First pass (i = 0, 1, 2) --- i=0, current=1 → stack empty → push 0 → stack: [0] i=1, current=2 → 2 > nums[0]=1 → pop 0, result[0]=2 → push 1 → stack: [1] i=2, current=1 → 1 < nums[1]=2 → push 2 → stack: [1, 2] --- Second pass (i = 3, 4, 5) — only pop, don't push --- i=3, current=nums[0]=1 → 1 < nums[2]=1 → no pop i=4, current=nums[1]=2 → 2 > nums[2]=1 → pop 2, result[2]=2 → 2 = nums[1]=2 → no pop (not strictly greater) i=5, current=nums[2]=1 → no pop Result: [2, -1, 2] ✅ ``` > The "iterate twice" trick for circular arrays is a pattern you'll see repeatedly. It works because modulo arithmetic lets you wrap around naturally, and you only need to go around once to give every element a chance to find its answer. ### Complexity | Metric | Complexity | |--------|-----------| | Time | O(n) — 2n iterations, each element pushed/popped at most once | | Space | O(n) — stack + result array | --- ## Stack Pattern #7: Daily Temperatures (LeetCode 739) Another monotonic stack classic, with a slightly different flavor. ### Problem > Given an array of integers `temperatures` representing daily temperatures, return an array `answer` where `answer[i]` is the number of days you have to wait after the `i`th day to get a warmer temperature. If there is no future day with a warmer temperature, `answer[i] = 0`. ### Example ``` Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73] Output: [1, 1, 4, 2, 1, 1, 0, 0] ``` ### The Key Insight "How many days until warmer" is really asking: "What's the distance to the next greater element?" Same monotonic stack pattern — but instead of recording the *value* of the next greater element, we record the *index difference*. ### TypeScript Solution ```typescript function dailyTemperatures(temperatures: number[]): number[] { const n = temperatures.length; const answer = new Array(n).fill(0); const stack: number[] = []; for (let i = 0; i < n; i++) { while ( stack.length > 0 && temperatures[stack[stack.length - 1]] < temperatures[i] ) { const prevDay = stack.pop()!; answer[prevDay] = i - prevDay; } stack.push(i); } return answer; } ``` ### Step-by-Step Walkthrough For `temperatures = [73, 74, 75, 71, 69, 72, 76, 73]`: ``` i=0, temp=73 → push 0 → stack: [0] i=1, temp=74 → 74 > 73 → pop 0, answer[0] = 1-0 = 1 → push 1 → stack: [1] i=2, temp=75 → 75 > 74 → pop 1, answer[1] = 2-1 = 1 → push 2 → stack: [2] i=3, temp=71 → 71 < 75 → push 3 → stack: [2, 3] i=4, temp=69 → 69 < 71 → push 4 → stack: [2, 3, 4] i=5, temp=72 → 72 > 69 → pop 4, answer[4] = 5-4 = 1 → 72 > 71 → pop 3, answer[3] = 5-3 = 2 → 72 < 75 → stop → push 5 → stack: [2, 5] i=6, temp=76 → 76 > 72 → pop 5, answer[5] = 6-5 = 1 → 76 > 75 → pop 2, answer[2] = 6-2 = 4 → push 6 → stack: [6] i=7, temp=73 → 73 < 76 → push 7 → stack: [6, 7] Remaining: indices 6, 7 → answer stays 0 Result: [1, 1, 4, 2, 1, 1, 0, 0] ✅ ``` Notice how when we hit 72 (day 5), it resolves *two* entries at once — both day 4 (69) and day 3 (71). The stack efficiently batches these resolutions. And when 76 shows up on day 6, it wipes out even more. This is why the total work stays O(n). ### Complexity | Metric | Complexity | |--------|-----------| | Time | O(n) — each index pushed and popped at most once | | Space | O(n) — stack stores indices | --- ## Stack Pattern #8: Largest Rectangle in Histogram (LeetCode 84) This is the **boss battle** of monotonic stack problems. It's a LeetCode Hard, it shows up in top-company interviews, and it's the foundation for problems like "maximal rectangle in a binary matrix." If you can nail this one, you truly understand monotonic stacks. ### Problem > Given an array of integers `heights` representing the histogram's bar heights (each bar has width 1), return the area of the largest rectangle in the histogram. ### Example ``` Input: heights = [2, 1, 5, 6, 2, 3] Output: 10 The largest rectangle has area 10 (heights 5 and 6, spanning 2 bars): 5 × 2 = 10... wait, let me visualize: ___ | | ___| | | | | ___ | | | ___| | | | | | | | _|___|___|_|___|___|_ 2 1 5 6 2 3 The rectangle spanning bars at index 2 and 3 (heights 5 and 6) with min height 5 and width 2 gives area = 5 × 2 = 10. ``` ### The Brute Force (to Understand the Problem) For every bar, you could expand left and right as far as possible while the bars are at least as tall. The width times the height gives the rectangle area. This is O(n²). We want O(n). ### The Key Insight For each bar, the largest rectangle using that bar's height extends from the **previous smaller bar** on the left to the **next smaller bar** on the right. The width of the rectangle is `rightBoundary - leftBoundary - 1`, and the height is the bar's height. We can find these boundaries using a monotonic *increasing* stack (from bottom to top). When a shorter bar arrives, taller bars get popped — and at the moment of popping, we know both boundaries: - **Right boundary**: the current index (the shorter bar that caused the pop) - **Left boundary**: the new top of the stack after popping (the previous shorter bar) ### TypeScript Solution ```typescript function largestRectangleArea(heights: number[]): number { const stack: number[] = []; let maxArea = 0; const n = heights.length; for (let i = 0; i <= n; i++) { const currentHeight = i === n ? 0 : heights[i]; while (stack.length > 0 && heights[stack[stack.length - 1]] > currentHeight) { const height = heights[stack.pop()!]; const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1; maxArea = Math.max(maxArea, height * width); } stack.push(i); } return maxArea; } ``` ### Why `i <= n` and `currentHeight = 0`? We iterate to `n` (one past the end) with a virtual height of 0. This forces all remaining bars in the stack to be popped and processed. Without this trick, bars that never encounter a shorter bar to their right would be left in the stack unprocessed. ### Step-by-Step Walkthrough For `heights = [2, 1, 5, 6, 2, 3]`: ``` i=0, h=2 → push 0 → stack: [0] i=1, h=1 → 1 < heights[0]=2 → pop 0 height = 2, stack is empty → width = i = 1 area = 2 × 1 = 2 → maxArea = 2 push 1 → stack: [1] i=2, h=5 → 5 > 1 → push 2 → stack: [1, 2] i=3, h=6 → 6 > 5 → push 3 → stack: [1, 2, 3] i=4, h=2 → 2 < heights[3]=6 → pop 3 height = 6, width = 4 - 2 - 1 = 1 area = 6 × 1 = 6 → maxArea = 6 2 < heights[2]=5 → pop 2 height = 5, width = 4 - 1 - 1 = 2 area = 5 × 2 = 10 → maxArea = 10 2 ≥ heights[1]=1 → stop push 4 → stack: [1, 4] i=5, h=3 → 3 > 2 → push 5 → stack: [1, 4, 5] i=6, h=0 (virtual) → triggers cleanup: pop 5: height = 3, width = 6 - 4 - 1 = 1, area = 3 pop 4: height = 2, width = 6 - 1 - 1 = 4, area = 8 pop 1: height = 1, stack empty → width = 6, area = 6 maxArea = 10 ✅ ``` ### Visualizing the Width Calculation The width formula `i - stack[stack.length - 1] - 1` deserves attention. When we pop an index: - `i` is the right boundary (the first shorter bar to the right) - `stack[stack.length - 1]` is the left boundary (the first shorter bar to the left) - The rectangle spans from `left + 1` to `right - 1`, which is `right - left - 1` bars wide When the stack is empty after popping, it means there's no shorter bar to the left — the rectangle extends all the way to index 0, so the width is simply `i`. > This problem is the ultimate monotonic stack test. Master it, and everything else in this category becomes manageable. The key insight: at the moment a bar is popped, you know both its left and right boundaries — and can compute its maximal rectangle instantly. ### Complexity | Metric | Complexity | |--------|-----------| | Time | O(n) — each bar pushed and popped at most once | | Space | O(n) — stack | --- ## Queue Pattern #1: Implement Stack Using Queues (LeetCode 225) Now let's shift to queue territory. These first two problems explore the fundamental relationship between stacks and queues. ### Problem > Implement a LIFO stack using only two queues. The stack should support `push`, `pop`, `top`, and `empty`. ### The Key Insight A queue is FIFO, a stack is LIFO — they're opposites. To make a queue behave like a stack, you need to reverse the order. The trick: after pushing an element to the queue, rotate all the *previous* elements behind it. Now the most recently pushed element is at the front. ### TypeScript Solution ```typescript class MyStack { private queue: number[] = []; push(x: number): void { this.queue.push(x); // Rotate everything before x to the back for (let i = 0; i < this.queue.length - 1; i++) { this.queue.push(this.queue.shift()!); } } pop(): number { return this.queue.shift()!; } top(): number { return this.queue[0]; } empty(): boolean { return this.queue.length === 0; } } ``` ### Step-by-Step Walkthrough ``` push(1) → queue: [1] → rotate 0 times → queue: [1] push(2) → queue: [1, 2] → rotate 1 time: shift 1, push 1 → queue: [2, 1] push(3) → queue: [2, 1, 3] → rotate 2 times: shift 2, push 2 → [1, 3, 2] shift 1, push 1 → [3, 2, 1] top() → 3 ✅ (most recently pushed is at front) pop() → 3 ✅ → queue: [2, 1] pop() → 2 ✅ → queue: [1] ``` Push is O(n), everything else is O(1). The rotation is the cost of turning FIFO into LIFO. ### Complexity | Metric | Complexity | |--------|-----------| | push | O(n) — rotation | | pop, top, empty | O(1) | | Space | O(n) | --- ## Queue Pattern #2: Implement Queue Using Stacks (LeetCode 232) The reverse problem — and arguably more interesting because of its amortized analysis. ### Problem > Implement a FIFO queue using only two stacks. The queue should support `push`, `pop`, `peek`, and `empty`. ### The Key Insight Use two stacks: an `input` stack for pushes and an `output` stack for pops. When the output stack is empty and you need to pop, pour everything from the input stack into the output stack. This reversal turns LIFO into FIFO. The clever part: you don't need to transfer on every operation. Each element is transferred at most once, giving **amortized O(1)** per operation. ### TypeScript Solution ```typescript class MyQueue { private input: number[] = []; private output: number[] = []; push(x: number): void { this.input.push(x); } pop(): number { this.transferIfNeeded(); return this.output.pop()!; } peek(): number { this.transferIfNeeded(); return this.output[this.output.length - 1]; } empty(): boolean { return this.input.length === 0 && this.output.length === 0; } private transferIfNeeded(): void { if (this.output.length === 0) { while (this.input.length > 0) { this.output.push(this.input.pop()!); } } } } ``` ### Step-by-Step Walkthrough ``` push(1) → input: [1], output: [] push(2) → input: [1, 2], output: [] peek() → output empty → transfer: input pops 2, 1 → output: [2, 1] → peek output top → 1 ✅ (FIFO: first in, first out) pop() → output: [2, 1] → pop → 1 ✅ → output: [2] push(3) → input: [3], output: [2] pop() → output not empty → pop → 2 ✅ → output: [] pop() → output empty → transfer: input pops 3 → output: [3] → pop → 3 ✅ ``` ### Why Amortized O(1)? Each element goes through at most these steps: pushed onto `input` (once), popped from `input` (once), pushed onto `output` (once), popped from `output` (once). That's 4 operations per element total. Even though a single `pop` might trigger an O(n) transfer, that transfer handles n elements, and those elements won't be transferred again. Averaged over all operations, each one is O(1). > This two-stack queue is a real-world pattern used in functional programming languages where queues are built from immutable lists (which are essentially stacks). It's not just an interview trick. ### Complexity | Metric | Complexity | |--------|-----------| | push | O(1) | | pop, peek | Amortized O(1) | | Space | O(n) | --- ## Queue Pattern #3: Number of Recent Calls (LeetCode 933) A simple but clean demonstration of the queue as a time window. ### Problem > Implement a `RecentCounter` class that counts the number of recent requests within a certain time frame. > - `ping(t)` — adds a new request at time `t` (milliseconds) and returns the number of requests that have happened in the past 3000 milliseconds (inclusive), i.e., in `[t - 3000, t]`. ### Example ``` ping(1) → requests in [−2999, 1] → [1] → 1 ping(100) → requests in [−2900, 100] → [1, 100] → 2 ping(3001) → requests in [1, 3001] → [1, 100, 3001] → 3 ping(3002) → requests in [2, 3002] → [100, 3001, 3002] → 3 ``` ### The Key Insight Requests arrive in chronological order. Old requests that fall outside the 3000ms window need to be removed. Since requests arrive in order, the oldest ones are at the front — this is a FIFO removal pattern. Queue. ### TypeScript Solution ```typescript class RecentCounter { private queue: number[] = []; ping(t: number): number { this.queue.push(t); while (this.queue[0] < t - 3000) { this.queue.shift(); } return this.queue.length; } } ``` ### Why a Queue? We add new timestamps to the back and remove expired ones from the front. That's exactly FIFO behavior. Each timestamp is added once and removed once, so the amortized time per `ping` is O(1). ### Complexity | Metric | Complexity | |--------|-----------| | Time per ping | Amortized O(1) | | Space | O(W) — where W is the number of requests in the time window | --- ## Queue Pattern #4: Sliding Window Maximum (LeetCode 239) This is a Hard problem and the queen of queue-based interview questions. It combines the sliding window technique with a **monotonic deque** — a data structure that's incredibly useful once you understand it. ### Problem > You are given an array of integers `nums` and a sliding window of size `k` that moves from left to right. Return the maximum value in each window position. ### Example ``` Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 Output: [3, 3, 5, 5, 6, 7] Window [1, 3, -1] → max = 3 Window [3, -1, -3] → max = 3 Window [-1, -3, 5] → max = 5 Window [-3, 5, 3] → max = 5 Window [5, 3, 6] → max = 6 Window [3, 6, 7] → max = 7 ``` ### Why Not Just Use a Regular Approach? The brute force is: for each window, scan all k elements to find the max. That's O(n × k). If `k` is large, this is too slow. You might think: "I'll use a max-heap (priority queue)!" That works, but removing elements from a heap is O(log n). We can do better. ### The Key Insight: Monotonic Deque A **deque** (double-ended queue) allows pushing and popping from *both* ends. A **monotonic deque** maintains a decreasing order from front to back. The front always holds the index of the current maximum. When a new element enters the window: 1. Remove indices from the **back** that point to values smaller than the new element (they'll never be the max — the new element is bigger and will be in the window longer). 2. Add the new element's index to the back. 3. Remove the **front** if it's outside the window. 4. The front of the deque is the current window's maximum. ### TypeScript Solution ```typescript function maxSlidingWindow(nums: number[], k: number): number[] { const result: number[] = []; const deque: number[] = []; // stores indices, decreasing order of values for (let i = 0; i < nums.length; i++) { // Remove elements from back that are smaller than current while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) { deque.pop(); } deque.push(i); // Remove front if it's outside the window if (deque[0] <= i - k) { deque.shift(); } // Window is fully formed starting at i = k - 1 if (i >= k - 1) { result.push(nums[deque[0]]); } } return result; } ``` ### Step-by-Step Walkthrough For `nums = [1, 3, -1, -3, 5, 3, 6, 7]`, `k = 3`: ``` i=0, num=1: deque empty → push 0 → deque: [0] window not full yet i=1, num=3: nums[0]=1 ≤ 3 → pop 0 → deque: [] push 1 → deque: [1] window not full yet i=2, num=-1: nums[1]=3 > -1 → don't pop push 2 → deque: [1, 2] i >= 2 → window full → max = nums[deque[0]] = nums[1] = 3 result: [3] i=3, num=-3: nums[2]=-1 > -3 → don't pop push 3 → deque: [1, 2, 3] deque[0]=1 ≤ 3-3=0? No (1 > 0) → keep max = nums[1] = 3 result: [3, 3] i=4, num=5: nums[3]=-3 ≤ 5 → pop 3 nums[2]=-1 ≤ 5 → pop 2 nums[1]=3 ≤ 5 → pop 1 push 4 → deque: [4] max = nums[4] = 5 result: [3, 3, 5] i=5, num=3: nums[4]=5 > 3 → don't pop push 5 → deque: [4, 5] max = nums[4] = 5 result: [3, 3, 5, 5] i=6, num=6: nums[5]=3 ≤ 6 → pop 5 nums[4]=5 ≤ 6 → pop 4 push 6 → deque: [6] max = nums[6] = 6 result: [3, 3, 5, 5, 6] i=7, num=7: nums[6]=6 ≤ 7 → pop 6 push 7 → deque: [7] max = nums[7] = 7 result: [3, 3, 5, 5, 6, 7] ✅ ``` ### Why the Deque Stays Small The deque never holds more than k elements, and often far fewer. Any element that's smaller than a newer element gets removed immediately — it's useless because the newer, larger element will outlast it in the window. The deque only keeps "potential maximums" in decreasing order. > The monotonic deque is what happens when you combine the monotonic stack idea with the sliding window idea. Stack-like behavior at the back (pop smaller elements), queue-like behavior at the front (remove expired elements). It's one of the most elegant data structure tricks in computer science. ### A Note on Performance In the solution above, `deque.shift()` is technically O(n) for a JavaScript array. For interview purposes, this is usually accepted. In production, you'd use a proper deque implementation (linked list or circular buffer) for true O(1) operations at both ends. Alternatively, you can use an index pointer instead of actually shifting: ```typescript function maxSlidingWindow(nums: number[], k: number): number[] { const result: number[] = []; const deque: number[] = []; let front = 0; for (let i = 0; i < nums.length; i++) { while (front < deque.length && nums[deque[deque.length - 1]] <= nums[i]) { deque.pop(); } deque.push(i); if (deque[front] <= i - k) { front++; } if (i >= k - 1) { result.push(nums[deque[front]]); } } return result; } ``` ### Complexity | Metric | Complexity | |--------|-----------| | Time | O(n) — each element enters and leaves the deque at most once | | Space | O(k) — deque stores at most k indices | --- ## The Monotonic Stack Deep Dive We've seen the monotonic stack show up in Next Greater Element, Daily Temperatures, and Largest Rectangle in Histogram. Let's pull out the pattern explicitly so you can apply it to *any* new problem. ### What "Monotonic" Means A **monotonic stack** maintains its elements in a consistent order — either non-increasing or non-decreasing from bottom to top. When a new element would violate the order, elements are popped until order is restored. Think of it like a bouncer at a club with a height requirement, but the requirement keeps changing based on who's showing up. ### Decreasing Stack (Next Greater Pattern) Elements decrease from bottom to top. When a larger element arrives, smaller elements get popped. Each popped element's "next greater" is the arriving element. **Use when**: you need to find the next *greater* element for each position. ```typescript // Template: next greater element function nextGreater(nums: number[]): number[] { const n = nums.length; const result = new Array(n).fill(-1); const stack: number[] = []; for (let i = 0; i < n; i++) { while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) { result[stack.pop()!] = nums[i]; } stack.push(i); } return result; } ``` ### Increasing Stack (Next Smaller Pattern) Elements increase from bottom to top. When a smaller element arrives, larger elements get popped. Each popped element's "next smaller" is the arriving element. **Use when**: you need to find the next *smaller* element for each position, or compute areas/spans bounded by smaller elements (like the histogram problem). ```typescript // Template: next smaller element function nextSmaller(nums: number[]): number[] { const n = nums.length; const result = new Array(n).fill(-1); const stack: number[] = []; for (let i = 0; i < n; i++) { while (stack.length > 0 && nums[stack[stack.length - 1]] > nums[i]) { result[stack.pop()!] = nums[i]; } stack.push(i); } return result; } ``` ### How to Decide Which Direction Ask yourself: **what relationship am I looking for?** | Looking for... | Stack type | Pop when... | |---------------|-----------|------------| | Next greater element | Decreasing | Current > stack top | | Next smaller element | Increasing | Current < stack top | | Previous greater element | Decreasing (iterate right to left) | Current > stack top | | Previous smaller element | Increasing (iterate right to left) | Current < stack top | ### The Four Variants You can get all four "next/previous greater/smaller" relationships by combining two choices: 1. **Comparison direction**: pop when `current > top` (greater) vs `current < top` (smaller) 2. **Iteration direction**: left-to-right (next) vs right-to-left (previous) This gives you a complete toolkit for problems involving element relationships. > Master one monotonic stack direction thoroughly. The others are just mirror images. Once the pattern clicks for "next greater," you can adapt it to any variant in seconds. --- ## Pattern Recognition: When to Think Stack or Queue You've seen a lot of problems now. Let's consolidate the recognition patterns so you can quickly identify the right data structure when you see a new problem. ### Reach for a Stack When You See... | Signal | Pattern | Example Problems | |--------|---------|-----------------| | Matching/nesting | Push open, pop to match close | Valid Parentheses, HTML tag validation | | "Next greater/smaller" | Monotonic stack | Next Greater Element, Daily Temperatures | | Expression evaluation | Operand stack | Reverse Polish Notation, Basic Calculator | | Undo/backtrack | Pop to undo most recent | Simplify Path, Backspace String Compare | | Maintain running min/max | Augmented stack | Min Stack | | Rectangle/area with boundaries | Monotonic stack for boundaries | Largest Rectangle, Trapping Rain Water | | Most recent context matters | General stack | Remove Adjacent Duplicates, Decode String | ### Reach for a Queue When You See... | Signal | Pattern | Example Problems | |--------|---------|-----------------| | Level-by-level processing | BFS queue | Binary tree level order, shortest path | | Sliding window optimization | Monotonic deque | Sliding Window Maximum | | FIFO ordering required | Standard queue | Task Scheduler, time-based operations | | Time window / expiration | Remove from front when expired | Number of Recent Calls | | Simulation / round-robin | Process in order, re-enqueue | Hot Potato, CPU scheduling | ### The Decision Flowchart When you're stuck on a new problem, run through these questions: 1. **Is there nesting or matching?** → Stack 2. **Does "most recent" context matter?** → Stack 3. **Are you looking for "next greater/smaller" relationships?** → Monotonic stack 4. **Do you need to process things in arrival order?** → Queue 5. **Is there a sliding window with a min/max query?** → Monotonic deque 6. **Level-by-level or shortest-path?** → BFS with queue --- ## Common Pitfalls (and How to Avoid Them) Even when you know the pattern, implementation bugs can trip you up. Here are the most common mistakes. ### 1. Popping from an Empty Stack ```typescript // 🚫 Crash waiting to happen const val = stack.pop()!; // ✅ Always guard if (stack.length > 0) { const val = stack.pop()!; } ``` In the Valid Parentheses problem, a closing bracket with an empty stack means unmatched brackets. In monotonic stack problems, the empty check is part of the `while` condition. Either way, never blindly pop. ### 2. Off-by-One in Width Calculations In the histogram problem, the width formula is: ```typescript const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1; ``` The `-1` accounts for the fact that the boundaries are *exclusive*. Forgetting it gives you widths that are one too large. If the stack is empty, the bar extends all the way to the left edge, so width is just `i`. ### 3. Forgetting the Cleanup Phase In monotonic stack problems, elements remaining in the stack after the main loop haven't found their "next" element. You need to either: - Process remaining elements after the loop, or - Add a sentinel value (like height 0 in the histogram problem) to force cleanup ```typescript // Sentinel approach — add a virtual element that's smaller than everything for (let i = 0; i <= n; i++) { const current = i === n ? 0 : heights[i]; // virtual 0 at the end // ... rest of monotonic stack logic } ``` ### 4. Wrong Monotonic Direction This is the trickiest pitfall. If you want "next greater," you need a stack where you pop elements *smaller* than the current. If you accidentally pop elements *larger* than the current, you'll get "next smaller" instead. Write out a small example (3-4 elements) and trace through before coding. It takes 30 seconds and saves 15 minutes of debugging. ### 5. Not Handling Circular Arrays For circular problems (Next Greater Element II), remember to iterate `2 * n` times and use `i % n`. Only push indices from the first pass (`i < n`), but pop during both passes. ### 6. Using Values When You Need Indices Monotonic stacks almost always store **indices**, not values. Indices let you: - Compute distances (Daily Temperatures) - Compute widths (Histogram) - Update the result array at the correct position If you're storing values, ask yourself if you actually need the index instead. --- ## Cheat Sheet ### Monotonic Stack Template (Next Greater) ```typescript function nextGreaterTemplate(nums: number[]): number[] { const n = nums.length; const result = new Array(n).fill(-1); const stack: number[] = []; // indices for (let i = 0; i < n; i++) { while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) { result[stack.pop()!] = nums[i]; } stack.push(i); } return result; } ``` ### Monotonic Deque Template (Sliding Window Max) ```typescript function slidingWindowMaxTemplate(nums: number[], k: number): number[] { const result: number[] = []; const deque: number[] = []; // indices, decreasing values for (let i = 0; i < nums.length; i++) { while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) { deque.pop(); } deque.push(i); if (deque[0] <= i - k) deque.shift(); if (i >= k - 1) result.push(nums[deque[0]]); } return result; } ``` ### Pattern → Problem Type Mapping | Pattern | Problem Type | Key Insight | |---------|-------------|------------| | Push open, pop to match | Bracket matching / nesting | Most recent unmatched opener | | Augmented stack (store min) | O(1) min/max queries | Cache derived values per level | | Operand stack | Expression evaluation | Operators consume top operands | | Directory stack (pop for `..`) | Path simplification | Stack = directory hierarchy | | Decreasing monotonic stack | Next greater element | Pop smaller, current is the answer | | Increasing monotonic stack | Next smaller / histogram | Pop larger, compute boundaries | | Circular + monotonic stack | Circular next greater | Iterate 2n, use modulo | | Two-stack queue | Amortized FIFO from LIFO | Lazy transfer on demand | | Monotonic deque | Sliding window min/max | Front = answer, back = maintenance | | Time-window queue | Recent calls / expiry | Remove from front when too old | ### Big O Reference | Operation | Time | Space | |-----------|------|-------| | Valid Parentheses | O(n) | O(n) | | Min Stack (all ops) | O(1) | O(n) | | Eval RPN | O(n) | O(n) | | Simplify Path | O(n) | O(n) | | Next Greater Element | O(n) | O(n) | | Daily Temperatures | O(n) | O(n) | | Largest Rectangle | O(n) | O(n) | | Sliding Window Maximum | O(n) | O(k) | | Two-Stack Queue (amortized) | O(1) per op | O(n) | --- ## What's Next? Stacks and queues are deceptively powerful. You've now seen that the *structure* is trivial — it's the *patterns* that matter. Valid parentheses, min tracking, monotonic stacks, expression evaluation, sliding window deques — these patterns recur across hundreds of interview problems. If you've been following the "Made Simple" series, here's how stacks and queues connect to what you already know: - **Arrays and Hashmaps** gave you the building blocks — stacks and queues are just arrays with discipline about which end you access - **Two Pointers and Sliding Window** taught you to think about ranges — the monotonic deque extends sliding windows with efficient min/max queries - **Recursion** uses the *call stack* — understanding stacks explicitly helps you convert recursive solutions to iterative ones - **Binary Search** taught you to eliminate half the search space — monotonic stacks achieve similar efficiency by ensuring each element is processed at most twice Coming up next in the series: - **Depth-First Search & Backtracking, Made Simple** — DFS is literally "use a stack (the call stack) to explore." Everything from tree traversals to sudoku solvers. - **Dynamic Programming, Made Simple** — the pattern that ties together everything you've learned --- ## Practice Roadmap Build your stack and queue fluency in this order. Start easy, build up. ### Tier 1: Stack Fundamentals | Problem | LeetCode # | Focus | |---------|-----------|-------| | Valid Parentheses | 20 | Basic stack matching | | Min Stack | 155 | Augmented stack | | Implement Queue using Stacks | 232 | Two-stack technique | | Baseball Game | 682 | Stack simulation | ### Tier 2: Monotonic Stack Basics | Problem | LeetCode # | Focus | |---------|-----------|-------| | Next Greater Element I | 496 | Monotonic stack introduction | | Daily Temperatures | 739 | Monotonic stack with distances | | Next Greater Element II | 503 | Circular array variant | | Remove K Digits | 402 | Monotonic stack for optimization | ### Tier 3: Expression and Path Processing | Problem | LeetCode # | Focus | |---------|-----------|-------| | Evaluate Reverse Polish Notation | 150 | Expression evaluation | | Simplify Path | 71 | Stack for path processing | | Basic Calculator II | 227 | Operator precedence | | Decode String | 394 | Nested stack processing | ### Tier 4: Advanced Monotonic Stack | Problem | LeetCode # | Focus | |---------|-----------|-------| | Largest Rectangle in Histogram | 84 | Boss battle monotonic stack | | Trapping Rain Water | 42 | Monotonic stack for boundaries | | Maximal Rectangle | 85 | 2D extension of histogram | | Sliding Window Maximum | 239 | Monotonic deque | > Don't rush through these. For each problem, before writing code, ask yourself: "What am I tracking? What's the relationship I'm looking for? Should elements be in increasing or decreasing order?" Build the habit of identifying the pattern first. --- ## Thanks for Reading If this guide helped stacks and queues click for you, share it with someone who's grinding LeetCode. The best way to lock in your understanding is to explain the monotonic stack to someone else — if you can walk through the Daily Temperatures example from memory, you own this pattern. Go solve a few problems. Start with Valid Parentheses if you haven't already, work up through the monotonic stack problems, and when you're ready, take on the Largest Rectangle in Histogram. That problem is the graduation exam — and you've got all the tools to pass it. Keep learning. Keep coding. You've got this. **Your Dev Brain, Now Thinking in Stacks and Queues** ---

Problem Solving Patterns: Stacks and Queues, Made Simple