DAY 18 / 30 · WEEK 3

Queues & Deques

Goal of the day

• Understand FIFO (first-in, first-out) queue mechanics — enqueue at the back, dequeue from the front — and contrast it with Day 17's stack (LIFO, both ends collapse to one).
• Understand a deque (double-ended queue): push and pop from both ends, front and back.
• Solve Sliding Window Maximum in O(n) using a monotonic deque of indices — instead of the naive O(n·k) approach of rescanning every window.

Concept

FIFO vs. LIFO. Day 17's stack is last-in, first-out: whatever you pushed most recently is the first thing that comes back out, and both push and pop happen at the same end. A queue flips that: it's first-in, first-out. Whoever enqueued first is the first one dequeued — think of a checkout line. Enqueue always adds to the back; dequeue always removes from the front. Those are two different ends, which is the key structural difference from a stack.

A JS gotcha worth knowing: a plain array works fine as a queue functionally (push to enqueue, shift to dequeue), but Array.prototype.shift() is O(n) — removing index 0 forces every remaining element to re-index down by one. A real O(1) queue needs a different structure (two stacks, a linked list, or an index-based circular buffer) — that's exactly what today's first two practice problems have you build.

A deque (pronounced "deck") generalizes both: you can push and pop from either end — pushFront/pushBack/popFront/popBack. A stack is a deque restricted to one end; a queue is a deque restricted to push-back/pop-front. Having both ends available is exactly what makes today's main algorithm possible.

Sliding Window Maximum. Given an array and a window size k, report the max of every contiguous window of size k as it slides across the array. The naive approach rescans all k elements for every one of the n - k + 1 windows: O(n·k). A monotonic deque gets this to O(n): keep a deque of indices whose values are strictly decreasing from front to back. The front index is always the current window's max. When a new element arrives, pop any smaller values off the back first — they can never win again, a bigger number just showed up behind them. Then push the new index onto the back. Finally, if the front index has slid outside the window, pop it from the front — even if it's still the largest value ever seen, it's no longer inside the window, so it doesn't count anymore.

Diagram: queue mechanics (FIFO)

Diagram: the monotonic deque's invariant

Interactive visualization: Sliding Window Maximum

The code: Sliding Window Maximum

function maxSlidingWindow(nums, k) {
  const deque = [];   // holds INDICES; front-to-back values strictly decrease
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    // 1. pop smaller trailing values off the BACK — they can never be the
    //    max again now that a bigger (or equal) number has shown up
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }

    // 2. push the current index onto the back
    deque.push(i);

    // 3. pop the FRONT if it has slid outside the window
    if (deque[0] <= i - k) {
      deque.shift();
    }

    // 4. once the window is full (i >= k - 1), the front is the max
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

Line by line:

• deque holds array indices, not values — storing values would make it impossible to tell whether the front has aged out of the window (you'd have no way to compare "position" against i - k).
• Step 1's while loop pops the back as long as it's ≤ the incoming value. This is what keeps the deque's invariant (strictly decreasing front-to-back) true after every push — an equal or smaller trailing value is provably useless from now on.
• Step 2 pushes i onto the back after the cleanup — the new element always ends up as a valid candidate.
• Step 3's check deque[0] <= i - k tests whether the front index is still inside the current window [i - k + 1, i]. If it isn't, it's evicted from the front — regardless of how large its value is.
• Step 4 only starts recording once the first full window exists (i >= k - 1); before that there simply isn't a complete window yet.

Dry run: maxSlidingWindow([5, 3, 8, 2, 9, 1, 7, 4], k = 3)

Final result: [8, 8, 9, 9, 9, 7]. Notice i=7: index 4 (value 9) is still the largest value ever seen, but it's outside the window [5, 6, 7] — position, not value, decides eviction from the front.

Complexity

Interview corner

• Why does the deque store indices instead of values? Storing values would make step 3 impossible — you need to compare the front's position against i - k to know whether it has slid outside the window. A raw value carries no position information at all.
  ⚠ Trap: this is the single most common way this pattern breaks in an interview — writing deque.push(nums[i]) instead of deque.push(i) compiles fine and even passes the first couple of test cases, then silently gives wrong answers once a stale-looking value needs to expire.
• Why is this O(n) despite the nested-looking while loop inside the for loop? Amortized analysis: each of the n indices is pushed onto the deque exactly once over the whole run, and can be popped at most once (from the back or the front) before it's gone for good. Total pushes + pops across the entire algorithm is bounded by 2n, not n·k — the nesting looks like O(n·k) but the inner loop's total work across all iterations is capped by how many elements exist, not by k.
  ↳ Common follow-up: "What if the array is strictly increasing?" — then every push immediately pops the entire deque from the back first, so the deque never holds more than 1 index; still O(n) overall, just a different distribution of the work.
• What's the deque's invariant, and why does maintaining it work? Front-to-back, the values at the stored indices strictly decrease. That's why the front is always the correct answer: anything that could have beaten it was already popped off the back before it could sit behind it.
• What happens if you forget to pop expired front indices before reading the max?
  ⚠ Trap: you'll silently return a max from an index that's no longer inside the current window — the code won't throw, it'll just be wrong, and easy to miss unless you specifically trace an example where the old max ages out (like i=7 in today's dry run).
• How is this different from Day 17's stack-based "next greater element" pattern? Both use a monotonic structure, but "next greater element" only ever pops from one end (a stack, LIFO). Sliding Window Maximum needs both ends — pop the back to maintain the value invariant, pop the front to enforce the window boundary — which is exactly why it needs a deque and not a plain stack.

How to talk through it out loud: name the invariant before you write a line of code — "I'll keep a deque of indices where the values are strictly decreasing front to back, so the front is always my current window's max." Then narrate the two eviction rules separately: "I pop the back when a new value makes an old one useless, and I pop the front when an old index slides outside the window." Interviewers are listening for whether you can articulate why each end gets popped, not just recite the code from memory.

Practice problems

Note: problem 3 (Sliding Window Maximum) is LeetCode Hard and is today's own core algorithm, not a step up in difficulty from problems 1-2 — same intentional exception to the usual easy→medium ramp used on Day 10 (Merge k Sorted Lists), since it's the natural, direct application of what this lesson just taught.

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

class MyCircularDeque {
  constructor(k) {
    this.cap = k;
    this.data = new Array(k);
    this.front = 0;
    this.size = 0;
  }
  insertFront(value) {
    if (this.size === this.cap) return false;
    this.front = (this.front - 1 + this.cap) % this.cap; // wrap backwards safely
    this.data[this.front] = value;
    this.size++;
    return true;
  }
  insertLast(value) {
    if (this.size === this.cap) return false;
    const rear = (this.front + this.size) % this.cap;
    this.data[rear] = value;
    this.size++;
    return true;
  }
  deleteFront() {
    if (this.size === 0) return false;
    this.front = (this.front + 1) % this.cap;
    this.size--;
    return true;
  }
  deleteLast() {
    if (this.size === 0) return false;
    this.size--; // rear is derived from size, so shrinking size "removes" it
    return true;
  }
  getFront() {
    return this.size === 0 ? -1 : this.data[this.front];
  }
  getRear() {
    return this.size === 0 ? -1 : this.data[(this.front + this.size - 1) % this.cap];
  }
  isEmpty() {
    return this.size === 0;
  }
  isFull() {
    return this.size === this.cap;
  }
}

function maxSlidingWindow(nums, k) {
  const deque = [];
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    while (deque.length && 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;
}

Quiz