Sliding Window Maximum

You are given an integer array nums and a window size k. Picture a frame exactly k elements wide placed over the start of the array. The frame then moves right one position at a time until its right edge reaches the last element, so there are n - k + 1 positions in total.

Return an array whose i-th entry is the largest value inside the frame when it covers nums[i] through nums[i + k - 1].

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

Pattern Path · Sliding Window · problem 56 of 169

Start simple

For every window position scan its k elements for the maximum: O(n·k) time, which is O(n²) when k is about n/2.

The key idea

The insight is that most elements in a window are hopeless. If nums[j] <= nums[i] and j < i, then as long as j is in the window, i is too, and it is at least as large. So j can be thrown away for good.

After discarding every hopeless element, the survivors form a sequence whose values strictly decrease from oldest to newest. Store their indices in a deque:

• When nums[i] arrives, pop from the back every index whose value is <= nums[i], then push i.
• If the front index is <= i - k, it has slid out of the frame, so pop it from the front.
• Once i >= k - 1, the front holds the window maximum.

Each index is pushed once and popped at most once, so the total work is linear even though a single step may pop many elements. Storing indices rather than values is what lets you tell when the front has expired.

Complexity

• Time: O(n)
• Space: O(k)

Python

class Solution:
    def maxSlidingWindow(self, nums, k):
        # Indices whose values are strictly decreasing from front to back.
        # The front is always the maximum of the current window.
        window = deque()
        result = []
        for i, x in enumerate(nums):
            # Smaller values behind x can never be a maximum again.
            while window and nums[window[-1]] <= x:
                window.pop()
            window.append(i)
            # Drop the front once it has slid out of the window.
            if window[0] <= i - k:
                window.popleft()
            if i >= k - 1:
                result.append(nums[window[0]])
        return result

JavaScript

var maxSlidingWindow = function(nums, k) {
  // Indices whose values are strictly decreasing from front to back,
  // stored in an array with a moving head pointer (an O(1) queue).
  const window = [];
  let head = 0;
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    // Smaller values behind nums[i] can never be a maximum again.
    while (window.length > head && nums[window[window.length - 1]] <= nums[i]) {
      window.pop();
    }
    window.push(i);
    // Drop the front once it has slid out of the window.
    if (window[head] <= i - k) head++;
    if (i >= k - 1) result.push(nums[window[head]]);
  }
  return result;
};

What the interviewer is checking

This tests whether you know the monotonic deque and can argue amortised O(n) cost: every index enters and leaves the deque at most once.

Mistakes to avoid

• Storing values instead of indices, which makes it impossible to know when the front has left the window.
• Removing the front only when its value equals the outgoing element, which breaks with duplicate values.
• Using a list with pop(0) (or shift() in JavaScript), which is O(k) per call and hides a quadratic cost.
• Starting to record answers before the first full window is formed.

Follow-ups to expect

• How would you return the window minimum instead? (Flip the comparison in the deque.)
• What if the numbers arrive as an unbounded stream? (Same deque, emit per arrival.)
• Can you do it without a deque? (Block prefix and suffix maxima.)

In real software

Monitoring dashboards show the peak latency or CPU load over the last k seconds, and trading systems track rolling highs; both use this rolling-maximum technique.

Practice next