Skip to main content

29. Sliding Window Maximum

hardAsked at Meta

Track the maximum value in a moving window — Meta's real-time engagement analytics and feed-ranking score smoothing rely on this monotonic deque pattern to compute rolling metrics over billions of events per day.

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

Problem

Given an integer array nums and an integer k, there is a sliding window of size k moving from the left to the right. Return an array of the maximums of each window position.

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]

Explanation: Window [1,3,-1] max=3; [3,-1,-3] max=3; [-1,-3,5] max=5; [-3,5,3] max=5; [5,3,6] max=6; [3,6,7] max=7.

Example 2

Input
nums = [1], k = 1
Output
[1]

Approaches

1. Brute force

For each window position compute the maximum by scanning k elements. Simple but O(n*k).

Time
O(n*k)
Space
O(1)
function maxSlidingWindow(nums, k) {
  const res = [];
  for (let i = 0; i <= nums.length - k; i++) {
    let max = -Infinity;
    for (let j = i; j < i + k; j++) max = Math.max(max, nums[j]);
    res.push(max);
  }
  return res;
}

Tradeoff:

2. Monotonic deque (optimal)

Maintain a deque of indices in decreasing order of values. The front always holds the index of the current window max. Evict out-of-window indices from the front; pop from the back any index whose value is smaller than the incoming element.

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

Tradeoff:

Meta-specific tips

Meta expects O(n) — the brute force will fail their time limits at n=10^5. The monotonic deque is the target pattern; explain its invariant out loud: the deque is always sorted decreasingly so the front is always the window max. Follow-up questions include minimum sliding window and how this generalizes to streaming aggregations in Meta's real-time data pipelines.

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

Practice these live with InterviewChamp.AI →