Skip to main content

23. Sliding Window Maximum

hardAsked at Chime

Return the maximum of every contiguous window of size k as it slides across the array.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an array of integers nums and a sliding window size k that moves from left to right of the array one position at a time, return the maximum value in each window as the window slides.

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

For each window position, scan k elements to find the max.

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 deque

Maintain a deque of indices whose values are strictly decreasing. Push the new index, pop the front when it falls out of the window, and the front always holds the current window's 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:

Chime-specific tips

Chime asks this when stress-testing balance-projection windows over high-frequency event streams, so cite the deque invariant explicitly before coding.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

More Chime coding interview questions

See all Chime problems →

Companies that also ask Sliding Window Maximum