Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Queue & Deque

Guide 1 of 6 · Path 1 of 6

PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Hardqueue-deque

Sliding Window Maximum

Problem (restated)

You are given an array nums and a window size k. Slide the window from left to right and return an array of the maximum value in each window.

Intuition

Brute force re-scans each window. The optimal idea: keep candidates for the max in a decreasing deque of indices. The front is always the current max. Drop indices that left the window, and drop back values that can never be max while a larger value is still in the window.

Approaches

Monotonic deque

Tested only
Time O(n)Space O(k)

Idea. Deque stores indices with decreasing nums values. For each i: (1) pop front if ≤ i-k, (2) pop back while nums[back] ≤ nums[i], (3) push i, (4) if i ≥ k-1, emit nums[front].

Walkthrough. nums = [1,3,-1,-3,5,3,6,7], k = 3 → [3,3,5,5,6,7]. When 5 arrives it clears the deque; front is always the answer for the live window.

Trade-offs. Each index enters/leaves once → O(n). Harder to invent than brute, but this is the expected hard solution.

Solution
export function maxSlidingWindow(nums: number[], k: number): number[] {
  const dq: number[] = [];
  const res: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    while (dq.length && dq[0]! <= i - k) dq.shift();
    while (dq.length && nums[dq[dq.length - 1]!]! <= nums[i]!) dq.pop();
    dq.push(i);
    if (i >= k - 1) res.push(nums[dq[0]!]!);
  }
  return res;
}

export function maxSlidingWindow(nums: number[], k: number): number[] {
  const dq: number[] = [];
  const res: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    while (dq.length && dq[0]! <= i - k) dq.shift();
    while (dq.length && nums[dq[dq.length - 1]!]! <= nums[i]!) dq.pop();
    dq.push(i);
    if (i >= k - 1) res.push(nums[dq[0]!]!);
  }
  return res;
}

Brute per window

Tested only
Time O(n·k)Space O(1)

Idea. For every window start, scan k elements for the max.

Walkthrough. Same input: correct but quadratic in the worst case (k ≈ n/2).

Trade-offs. Use only to validate or for tiny k. Interviews want the deque once n is large.

Solution
/** O(n*k) scan each window, baseline to beat with the deque. */
export function maxSlidingWindowBrute(nums: number[], k: number): number[] {
  const res: number[] = [];
  for (let i = 0; i <= nums.length - k; i++) {
    let m = -Infinity;
    for (let j = i; j < i + k; j++) m = Math.max(m, nums[j]!);
    res.push(m);
  }
  return res;
}

/** O(n*k) scan each window, baseline to beat with the deque. */
export function maxSlidingWindowBrute(nums: number[], k: number): number[] {
  const res: number[] = [];
  for (let i = 0; i <= nums.length - k; i++) {
    let m = -Infinity;
    for (let j = i; j < i + k; j++) m = Math.max(m, nums[j]!);
    res.push(m);
  }
  return res;
}

Template connection

Queue & deque window extrema: monotonic deque template.

Common bugs

Reflection