Deque

Overview

A deque (double-ended queue) supports insertion and removal at both the front and the back in O(1). It generalizes both a stack and a queue.

Its star use in algorithms is the monotonic deque: keep indexes in the deque so their values are always decreasing (or increasing). Then the maximum (or minimum) of a sliding window is at the front, and each element is added and removed at most once, giving O(n) for all windows.

When to use it

• You need both stack-like and queue-like operations.
• Maximum or minimum of every sliding window.
• 0-1 BFS: edges of weight 0 go to the front, weight 1 to the back.
• Palindrome checks and problems that consume from both ends.

Problem patterns it solves

Where it is used in real software

Key terms

offerFirst / offerLast

Insert at front / back (unshift / push in JS).

pollFirst / pollLast

Remove from front / back (shift / pop in JS).

Monotonic deque

Values of stored indexes are kept strictly decreasing (for max) or increasing (for min).

Expired index

An index that has left the window: index <= i - k.

Sliding window maximum with a monotonic deque

1. 1
   Store indexes, not values

   Indexes let you tell when an element has left the window.

2. 2
   Remove expired front

   If deque.front <= i - k, remove it from the front.

3. 3
   Remove smaller values from the back

   While nums[deque.back] <= nums[i], pop the back. Those elements can never be a maximum again, because nums[i] is larger and will stay in the window longer.

4. 4
   Push i to the back

   The deque stays decreasing from front to back.

5. 5
   Read the answer

   Once i >= k - 1, nums[deque.front] is the window maximum.

Deque state for sliding window maximum

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

Output [3, 3, 5, 5, 6, 7]. Each index enters and leaves the deque once, so the whole run is O(n) instead of O(n x k).

Implementation

1// A head index keeps shift() O(1) for this algorithm2function maxSlidingWindow(nums, k) {3  const dq = [];4  let head = 0;5  const result = [];6  for (let i = 0; i < nums.length; i++) {7    if (head < dq.length && dq[head] <= i - k) head++;          // expired front8    while (dq.length > head && nums[dq.at(-1)] <= nums[i]) dq.pop(); // weaker back9    dq.push(i);10    if (i >= k - 1) result.push(nums[dq[head]]);11  }12  return result;13}14 15// 1438: two deques track window max and min at the same time16function longestSubarray(nums, limit) {17  const maxDq = [], minDq = [];18  let left = 0, best = 0;19  for (let right = 0; right < nums.length; right++) {20    while (maxDq.length && maxDq.at(-1) < nums[right]) maxDq.pop();21    while (minDq.length && minDq.at(-1) > nums[right]) minDq.pop();22    maxDq.push(nums[right]);23    minDq.push(nums[right]);24    while (maxDq[0] - minDq[0] > limit) {25      if (maxDq[0] === nums[left]) maxDq.shift();26      if (minDq[0] === nums[left]) minDq.shift();27      left++;28    }29    best = Math.max(best, right - left + 1);30  }31  return best;32}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Storing values instead of indexes.

  Fix: Without indexes you cannot detect when the front has left the window.

• Using < instead of <= when popping.

  Fix: Either works for correctness in max problems, but <= keeps the deque smaller; be consistent with duplicates when storing values.

• Recording answers before the first full window.

  Fix: Only record when i >= k - 1.

Interview questions

Practice problems