🔧 JavaScript Stack & Queue Patterns

Pattern 1 — Monotonic Stack (Next Greater Element)

🧠 How to Approach This

Step 1 — Recognize the pattern: "Next greater/smaller" → monotonic stack. Keywords: daily temperatures, next warmer day, stock span.

Step 2 — Brute force (what NOT to do): Nested loops — O(n²).

Step 3 — Optimal insight: Decreasing stack of indices. When larger element arrives, it's the answer for everything it pops.

Step 4 — Algorithm:

1. Stack of unresolved indices

2. For each i: while stack.top's value < nums[i] → answer[pop] = nums[i]

3. Push i

Step 5 — Edge cases: No greater successor → stays -1.

function nextGreaterElement(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack  = []; // indices

  for (let i = 0; i < n; i++) {
    while (stack.length && nums[stack.at(-1)] < nums[i]) {
      result[stack.pop()] = nums[i];
    }
    stack.push(i);
  }
  return result;
}
// [2,1,3,4] → [3,3,4,-1]

Time: O(n) — each element pushed/popped once | Space: O(n)

---

Pattern 2 — Monotonic Stack (Daily Temperatures)

Same pattern — answer is distance not value.

🧠 How to Approach This

Step 1 — Recognize the pattern: "Days until warmer" → result = i - popped_i.

Step 2 — Brute force (what NOT to do): Nested loops — O(n²).

Step 3 — Optimal insight: Monotonic decreasing stack of indices. When warmer temp found, result[pop] = i - pop.

Step 4 — Algorithm:

1. Stack of indices (decreasing temps)

2. Each element: while top's temp < current → result[pop] = i - pop

3. Push i

Step 5 — Edge cases: Last element — no warmer day → 0.

function dailyTemperatures(temps) {
  const n = temps.length;
  const result = new Array(n).fill(0);
  const stack  = [];

  for (let i = 0; i < n; i++) {
    while (stack.length && temps[stack.at(-1)] < temps[i]) {
      const idx    = stack.pop();
      result[idx]  = i - idx;
    }
    stack.push(i);
  }
  return result;
}

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

---

Pattern 3 — Sliding Window Maximum (Monotonic Deque)

🧠 How to Approach This

Step 1 — Recognize the pattern: Maximum in a sliding window of size k.

Step 2 — Brute force (what NOT to do): Scan k elements per window — O(n·k).

Step 3 — Optimal insight: Monotonic decreasing deque of indices. Front = current max. Remove expired from front; remove smaller from back.

Step 4 — Algorithm:

1. Remove out-of-window indices from front

2. Remove smaller elements from back

3. Append result when i >= k-1

Step 5 — Edge cases: k = 1; k > n.

function maxSlidingWindow(nums, k) {
  const n = nums.length;
  const result = [];
  const deque  = []; // indices, monotonic decreasing

  for (let i = 0; i < n; i++) {
    // Remove out-of-window from front
    while (deque.length && deque[0] < i - k + 1) deque.shift();
    // Remove smaller from back
    while (deque.length && nums[deque.at(-1)] < nums[i]) deque.pop();
    deque.push(i);
    if (i >= k - 1) result.push(nums[deque[0]]);
  }
  return result;
}

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

---

Pattern 4 — Implement Queue Using Two Stacks

🧠 How to Approach This

Step 1 — Recognize the pattern: Two LIFO structures → FIFO via lazy transfer.

Step 2 — Brute force (what NOT to do): Transfer on every push or pop — O(n) each.

Step 3 — Optimal insight: Only transfer when outStack is empty — amortized O(1).

Step 4 — Algorithm:

1. push → inStack

2. pop/peek: if outStack empty, drain inStack into outStack

Step 5 — Edge cases: Mixed push/pop sequences.

class MyQueue {
  constructor() { this.inStack = []; this.outStack = []; }
  push(x) { this.inStack.push(x); }
  pop()   { this._transfer(); return this.outStack.pop(); }
  peek()  { this._transfer(); return this.outStack.at(-1); }
  empty() { return !this.inStack.length && !this.outStack.length; }
  _transfer() {
    if (!this.outStack.length)
      while (this.inStack.length) this.outStack.push(this.inStack.pop());
  }
}

Time: O(1) amortized | Space: O(n)

---

Pattern 5 — Largest Rectangle in Histogram

🧠 How to Approach This

Step 1 — Recognize the pattern: Monotonic increasing stack — pop when shorter bar arrives.

Step 2 — Brute force (what NOT to do): All bar pairs — O(n²).

Step 3 — Optimal insight: Each popped bar defines a rectangle; width = i - new_stack_top - 1.

Step 4 — Algorithm:

1. Append sentinel 0 to heights

2. Stack starts with [-1]

3. On pop: area = height × (i - stack.top - 1)

Step 5 — Edge cases: Sentinel forces all bars to be processed at end.

function largestRectangleArea(heights) {
  heights = [...heights, 0]; // sentinel
  const stack = [-1];
  let maxArea = 0;

  for (let i = 0; i < heights.length; i++) {
    while (stack.at(-1) !== -1 && heights[stack.at(-1)] > heights[i]) {
      const height = heights[stack.pop()];
      const width  = i - stack.at(-1) - 1;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }
  return maxArea;
}

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