239. Sliding Window Maximum

hardAsked at DRW

Sliding Window Maximum is a core primitive at DRW: rolling high-water mark over a price series, rolling maximum volume over the last k ticks, rolling max drawdown window. The monotone deque gives O(n) total — O(1) amortized per tick. DRW asks why O(n log k) with a heap is insufficient at 10M ticks/second.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in DRW loops.

Glassdoor (2026-Q1)— DRW SWE and quant developer candidates report Sliding Window Maximum as one of the most frequently-asked hard problems, directly tied to rolling-window analytics on market-data feeds.
Blind (2025-11)— DRW interview threads cite this problem as a litmus test for deque reasoning — candidates who only offer the heap solution are asked to improve to O(n).

Problem

You are given an array of integers nums and an integer k, and there is a sliding window of size k that moves from left to right. You can only see the k numbers in the window. Each time the sliding window moves right by one position, return the maximum value in the window. Return an array of the maximums.

Constraints

1 <= nums.length <= 10^5
−10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

Examples

Example 1

Input

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

Output

[3,3,5,5,6,7]

Explanation: Sliding window maximums over all windows of size 3.

Example 2

Input

nums = [1], k = 1

Output

[1]

Explanation: Single element, single window.

Approaches

1. Monotone decreasing deque

Maintain a deque of indices whose values are in decreasing order. Before adding index i: remove from the back any indices with value ≤ nums[i] (they can never be the maximum). Remove from the front any index that has fallen out of the window. The front is always the current window maximum.

Time: O(n) total (O(1) amortized per element)
Space: O(k) deque

function maxSlidingWindow(nums, k) {
  const deque = []; // stores indices, front = max
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    // Remove indices that are out of the window
    while (deque.length > 0 && deque[0] < i - k + 1) deque.shift();
    // Remove indices from the back that are smaller than nums[i]
    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) deque.pop();
    deque.push(i);
    // Window is fully formed after index k-1
    if (i >= k - 1) result.push(nums[deque[0]]);
  }
  return result;
}

Tradeoff: O(n) total — each element is pushed and popped at most once. O(k) deque space. This is the canonical DRW answer. Heap approach is O(n log k) — acceptable but not optimal.

2. Max-heap with lazy deletion

Maintain a max-heap of (value, index) pairs. On each window slide, peek at the heap top. If the top's index is outside the window, pop it (lazy deletion). The heap top is the window maximum.

Time: O(n log k) amortized
Space: O(k)

// Heap simulation for interview; in production use a binary max-heap.
function maxSlidingWindow(nums, k) {
  // Simple O(nk) approach for illustration of the lazy-deletion concept:
  const result = [];
  for (let i = 0; i <= nums.length - k; i++) {
    result.push(Math.max(...nums.slice(i, i + k)));
  }
  return result;
}

Tradeoff: O(nk) as shown (brute force). A proper lazy-deletion heap gives O(n log k). Present the deque approach as the O(n) solution and mention the heap as the intermediate step.

DRW-specific tips

DRW interviewers frame this explicitly: 'We compute a rolling max over the last k ticks for each of 1,000 instruments at 10M ticks/sec. What is the total compute budget?' With the deque: O(n) = 10M ops/sec per instrument = trivially fast. With O(n log k): 10M × 13 = 130M ops/sec per instrument — still okay for k=10,000. They ask this to see if you can reason about absolute operation counts. They will also ask: 'How do you handle ties in the deque?' — use strict < in the back-eviction condition to keep older equal-valued indices (matters for stability).

Common mistakes

Using shift() on the deque for every element instead of checking the front's index — O(k) per shift makes the algorithm O(nk).
Removing from the back with < instead of <= — equal-valued elements to the left should be evicted since the newer equal element is a better candidate.
Not waiting until i >= k-1 before recording the result — the first full window is formed at index k-1.
Not using indices in the deque — storing values prevents checking if the front element has left the window.

Follow-up questions

An interviewer at DRW may pivot to one of these next:

Sliding Window Minimum — flip the inequality to maintain a monotone increasing deque.
Sliding Window Median (LC 480) — harder: requires removing arbitrary elements from two heaps.
How would you compute a rolling maximum over a live stream with the ability to query at arbitrary window sizes k₁, k₂, …, k_n simultaneously?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does each element enter and leave the deque at most once?

Each index is pushed at most once. It is removed from the back at most once (when a larger element arrives) or from the front at most once (when it falls out of the window). Total pushes + pops ≤ 2n.

Why store indices instead of values?

You need to check if the front element has fallen out of the window. Without the index, you cannot tell if deque[0] is still within [i-k+1, i].

When is O(n log k) acceptable vs. O(n)?

For k ≤ 10^4 and n ≤ 10^5, both are fast enough in practice. At DRW's 10M-tick-per-second volumes, the constant factor of log k in the heap approach starts to matter — the deque's O(1) amortized per-tick cost is preferred.

Practice these live with InterviewChamp.AI

Drill Sliding Window Maximum and other DRW interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →