Stacks & Queues

How to recognize it

Stack problems involve matching, nesting, or undoing — valid parentheses, evaluating a nested expression, implementing undo, finding the nearest larger or smaller element in either direction. The common thread is that the most recently seen unmatched item is the one you need next, which is exactly what a stack gives you for free (last in, first out).

Queue problems involve arrival order — the first thing seen must be the first thing processed. This shows up far more often as a supporting structure inside another algorithm (breadth-first search) than as the entire problem itself.

How the pattern works

A representative stack problem: for each element in an array, find the next element to its right that is strictly greater ("daily temperatures"-style). The brute force checks every pair — O(n²). A monotonic decreasing stack solves it in one pass: push indices while the stack's top is greater than or equal to the current value; when the current value is larger, it is the answer for everything you just popped.

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []  # indices, values decreasing bottom to top
    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            j = stack.pop()
            result[j] = num
        stack.append(i)
    return result

function nextGreater(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = []; // indices, values decreasing bottom to top
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      const j = stack.pop();
      result[j] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

Name the invariant: "the stack holds indices whose values are decreasing from bottom to top — anything smaller than the current value gets popped and resolved right now." That single sentence is what separates a monotonic stack from "a stack that happens to work here."

Common mistakes

• Pushing values instead of indices — most monotonic-stack problems need the index to write into a result array or compute a distance, not just the value itself
• Confusing increasing and decreasing monotonic stacks — "next greater" needs a decreasing stack; "next smaller" needs an increasing one, and mixing them up gives silently wrong answers, not a crash
• Using a stack for a problem that is actually about arrival order (should be a queue) because "stack or queue" gets treated as interchangeable under pressure
• Forgetting to clarify what happens when no matching element exists (return -1? null? throw?) before writing the code

Complexity

A monotonic stack solution is O(n) time despite the nested loop in the code, for the same reason as sliding window: every index is pushed once and popped at most once, so the total work across all iterations of the inner while loop is bounded by n, not n². Space is O(n) for the stack in the worst case (a strictly increasing input never pops anything). Stating the amortized argument explicitly — "it looks like O(n²) but each element is pushed and popped at most once" — is exactly the kind of complexity defense covered in Time & Space Complexity.