Skip to main content

89. Sliding Window Maximum

hardAsked at Datadog

Return the max of each sliding window of size k. Datadog asks this constantly — the monotonic deque is the exact algorithm they use for streaming max-over-window aggregations on real-time metric dashboards.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — graded on monotonic deque.
  • Blind (2025-12)— Most frequent Datadog hard problem.
  • LeetCode Discuss (2025-11)— Recurring Datadog onsite.

Problem

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

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]

Example 2

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

Approaches

1. Recompute max per window

O(k) max per position.

Time
O(n * k)
Space
O(1)
// For each i, scan i..i+k-1 for max.

Tradeoff: n*k. Datadog will fail for 10^5 * 10^5.

2. Monotonic deque (optimal)

Deque holds INDICES with values in decreasing order. Pop from back while smaller-or-equal value; pop from front if out of window. Front IS the max.

Time
O(n)
Space
O(k)
function maxSlidingWindow(nums, k) {
  const dq = []; // store indices, values decreasing
  const out = [];
  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) out.push(nums[dq[0]]);
  }
  return out;
}

Tradeoff: O(n) — each index pushed and popped at most once. Datadog-canonical: the exact pattern they use for max-over-window streaming aggregation.

Datadog-specific tips

Datadog grades on the monotonic deque invariant: values strictly decreasing from front to back; front is the current window max. Articulate the invariant and amortized O(1) per element BEFORE coding.

Common mistakes

  • Using JS Array.shift (O(n)) instead of a proper deque — pessimizes to O(n^2). For Datadog scale, use index head pointer.
  • Comparing dq[0] === i - k + 1 instead of dq[0] <= i - k — off by one.
  • Storing values instead of indices — can't tell when the front falls out of window.

Follow-up questions

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

  • Sliding Window Median (LC 480).
  • Constrained Subsequence Sum (LC 1425) — same deque pattern in DP.
  • Datadog-style: streaming max-over-window for real-time metric aggregation.

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 store indices not values?

We need to know when a value falls out of the window. The index lets us compare against i - k.

Why amortized O(1)?

Each index is pushed once and popped at most once. Total work across all positions is O(n).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →