Skip to main content

23. Sliding Window Maximum

hardAsked at Baidu

For each window of size k in an array, return the maximum value in linear total time.

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

Problem

Given an integer array nums and an integer k, return an array of the maximum value in every contiguous window of size k. The total runtime must be linear in nums.length.

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. Max of each window

For each window, sweep its k elements for the maximum.

Time
O(n * k)
Space
O(1)
const out=[];for(let i=0;i+k<=nums.length;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 of indices

Maintain a deque of indices whose values are strictly decreasing; the front is always the max of the current window. Pop the back while it is smaller than the new value; pop the front when it falls out of the window.

Time
O(n)
Space
O(k)
function maxSlidingWindow(nums, k) {
  const dq = []; // indices, values strictly decreasing
  const out = [];
  for (let i = 0; i < nums.length; i++) {
    while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
    dq.push(i);
    if (dq[0] <= i - k) dq.shift();
    if (i >= k - 1) out.push(nums[dq[0]]);
  }
  return out;
}

Tradeoff:

Baidu-specific tips

Baidu uses this exact deque-of-indices to compute rolling max-bid in ad-ranking auctions, so they expect the linear-time deque solution and a quick proof that each index enters and exits the deque at most once.

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

Practice these live with InterviewChamp.AI →