89. Sliding Window Maximum
hardAsked at DatadogReturn 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 Sam K., 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^41 <= k <= nums.length
Examples
Example 1
nums = [1,3,-1,-3,5,3,6,7], k = 3[3,3,5,5,6,7]Example 2
nums = [1], k = 1[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.
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).