Skip to main content

31. Sliding Window Maximum

hardAsked at Doordash

Return the maximum value in each sliding window of size k — Doordash uses this deque pattern in their real-time demand forecasting: finding peak order rates over every rolling k-minute window to trigger Dasher surge dispatch.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an integer array nums and an integer k. There is a sliding window of size k moving from the left to the right of the array. You can only see the k numbers in the window. Return an array of the maximum value in each window position.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= k <= nums.length
  • -10^4 <= nums[i] <= 10^4
  • You should solve this in O(n) time

Examples

Example 1

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

Explanation: Windows: [1,3,-1]->3, [3,-1,-3]->3, [-1,-3,5]->5, [-3,5,3]->5, [5,3,6]->6, [3,6,7]->7.

Example 2

Input
nums = [1], k = 1
Output
[1]

Approaches

1. Brute force per window

For every window of size k, scan all k elements to find the max. Simple but O(nk).

Time
O(n*k)
Space
O(1) extra
function maxSlidingWindow(nums, k) {
  const result = [];
  for (let i = 0; i <= nums.length - k; i++) {
    let max = -Infinity;
    for (let j = i; j < i + k; j++) {
      max = Math.max(max, nums[j]);
    }
    result.push(max);
  }
  return result;
}

Tradeoff:

2. Monotonic deque (decreasing)

Maintain a deque of indices in decreasing order of their values. On each step: remove indices out of window from the front; remove smaller indices from the back (they can never be a future max); push current index; front is the current max.

Time
O(n)
Space
O(k)
function maxSlidingWindow(nums, k) {
  const deque = [];
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    while (deque.length && deque[0] < i - k + 1) deque.shift();
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) deque.pop();
    deque.push(i);
    if (i >= k - 1) result.push(nums[deque[0]]);
  }
  return result;
}

Tradeoff:

Doordash-specific tips

Doordash expects the monotonic deque solution and wants you to articulate the invariant clearly: 'the deque is always in decreasing order of value, so the front is always the window max.' The common mistake is forgetting to evict from the front when the window slides past an index — state this eviction condition aloud before coding. They follow up with: 'what if the window size k changes dynamically?' — that requires a segment tree or sparse table for range-max in O(1) after O(n log n) preprocessing.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →