Algorithmshard

What is a monotonic stack and what kind of problems does it solve?

Answer

A monotonic stack keeps elements in increasing or decreasing order. It’s used for “next greater/smaller element”, stock span, and histogram problems, often in O(n) time by pushing/popping each element at most once.

function nextGreater(nums: number[]): number[] {
  const res = Array(nums.length).fill(-1);
  const st: number[] = []; // stack of indices

  for (let i = 0; i < nums.length; i++) {
    while (st.length && nums[st[st.length - 1]] < nums[i]) {
      res[st.pop()!] = nums[i];
    }
    st.push(i);
  }

  return res;
}

Advanced answer

Deep dive

Expanding on the short answer — what usually matters in practice:

Context (tags): stack, monotonic-stack, next-greater, big-o
Complexity: compare typical operations (average vs worst-case).
Invariants: what must always hold for correctness.
When the choice is wrong: production symptoms (latency, GC, cache misses).
Explain the "why", not just the "what" (intuition + consequences).
Trade-offs: what you gain/lose (time, memory, complexity, risk).
Edge cases: empty inputs, large inputs, invalid inputs, concurrency.

Examples

Here’s an additional example (building on the short answer):

function nextGreater(nums: number[]): number[] {
  const res = Array(nums.length).fill(-1);
  const st: number[] = []; // stack of indices

  for (let i = 0; i < nums.length; i++) {
    while (st.length && nums[st[st.length - 1]] < nums[i]) {
      res[st.pop()!] = nums[i];
    }
    st.push(i);
  }

  return res;
}

Common pitfalls

Too generic: no concrete trade-offs or examples.
Mixing average-case and worst-case (e.g., complexity).
Ignoring constraints: memory, concurrency, network/disk costs.

Interview follow-ups

When would you choose an alternative and why?

Related questions

Algorithms

Quickselect: what is it used for and what is its expected complexity?

#quickselect#selection#partition

Algorithms

What is a monotonic queue and how does it solve sliding window max in O(n)?

#deque#monotonic-queue#sliding-window

Algorithms

Counting sort: when can it be faster than O(n log n)

Answer

function nextGreater(nums: number[]): number[] {
  const res = Array(nums.length).fill(-1);
  const st: number[] = []; // stack of indices

  for (let i = 0; i < nums.length; i++) {
    while (st.length && nums[st[st.length - 1]] < nums[i]) {
      res[st.pop()!] = nums[i];
    }
    st.push(i);
  }

  return res;
}

Advanced answer

Deep dive

Expanding on the short answer — what usually matters in practice:

Context (tags): stack, monotonic-stack, next-greater, big-o
Complexity: compare typical operations (average vs worst-case).
Invariants: what must always hold for correctness.
When the choice is wrong: production symptoms (latency, GC, cache misses).
Explain the "why", not just the "what" (intuition + consequences).
Trade-offs: what you gain/lose (time, memory, complexity, risk).
Edge cases: empty inputs, large inputs, invalid inputs, concurrency.

Examples

Here’s an additional example (building on the short answer):

function nextGreater(nums: number[]): number[] {
  const res = Array(nums.length).fill(-1);
  const st: number[] = []; // stack of indices

  for (let i = 0; i < nums.length; i++) {
    while (st.length && nums[st[st.length - 1]] < nums[i]) {
      res[st.pop()!] = nums[i];
    }
    st.push(i);
  }

  return res;
}

Common pitfalls

Too generic: no concrete trade-offs or examples.
Mixing average-case and worst-case (e.g., complexity).
Ignoring constraints: memory, concurrency, network/disk costs.

Interview follow-ups

When would you choose an alternative and why?