Skip to main content

23. Sliding Window Maximum

hardAsked at Activision

Return the max of every length-k sliding window — Activision uses this to gauge monotonic-deque reasoning before anti-cheat telemetry burst-detection questions.

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

Problem

Given an array nums and a sliding window of size k that moves from left to right, return the maximum of each window. Output has length nums.length - k + 1.

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. Per-window scan

Compute max of each window by iterating k elements.

Time
O(n*k)
Space
O(1)
const out = [];
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]);
  out.push(m);
}
return out;

Tradeoff:

2. Monotonic decreasing deque

Maintain deque of indices with strictly decreasing values. Front is always the window max. Pop from front when index falls out of window; pop from back when smaller value arrives.

Time
O(n)
Space
O(k)
function maxSlidingWindow(nums, k) {
  const dq = [];
  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:

Activision-specific tips

Activision watches for the monotonic-deque insight — same shape they use when scanning anti-cheat telemetry windows for short-burst hack signatures in real time.

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 Activision interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →