Skip to main content

25. Sliding Window Maximum

hardAsked at ByteDance

Return the maximum of every sliding window of size k — ByteDance uses it because it mirrors how their ranking engine summarizes engagement signals over rolling windows.

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

Problem

Given an integer array nums and a window size k, return an array of the maximum value within each contiguous window of size k as it slides from left to right.

Constraints

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

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 max

For each window, scan its k elements and take the max.

Time
O(n * k)
Space
O(1)
for(let i=0;i+k<=n;i++){ let m=-Infinity; for(let j=i;j<i+k;j++) m=Math.max(m,nums[j]); out.push(m); }

Tradeoff:

2. Monotonic deque of indices

Maintain a deque of indices whose values strictly decrease. Pop smaller tail values when pushing, pop the head when it leaves the window, then the head is the window max.

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:

ByteDance-specific tips

ByteDance interviewers want the monotonic-deque invariant stated up front because the same data structure powers rolling-engagement maxima inside their feed ranker.

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

Practice these live with InterviewChamp.AI →