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 Sam K., 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

More ByteDance coding interview questions

See all ByteDance problems →

Companies that also ask Sliding Window Maximum